7.3. Модификация быстрой сортировки

RandomizedQuickSort(c):
     if |c| <= 1: # тут и сортировать нечего
        return c
     m = random_choice(c) # выбираем случайный элемент из массива
     определяем элементы c_small меньшие m 
     определяем элементы c_large большие m
     RandomizedQuickSort(c_small) # рекурсивный вызов алгоритма
     RandomizedQuickSort(c_large)
     объединяем c_small, m и c_large в итоговый массив c_sorted
     return c_sorted

В этом псевдокоде подразумевается, что все элементы массива разные. Ожидаемое время выполнения алгоритма составляет .

Алгоритм легко изменить для случая, когда в этом массиве есть повторы. Чтобы это сделать, пусть в содержатся все элементы со значением не более , а не элементы со значением менее . Тем не менее такая модификация становится медленной даже относительно ожидаемого времени выполнения. Например, если все элементы одинаковы, разделяется на две части: размер составляет , а в нет элементов. Так как это разделение требует от RandomizedQuickSort времени , общее время выполнения составляет:

то есть вместо .

Ваша цель — изменить описанный выше алгоритм RandomizedQuickSort так, чтобы даже при последовательностях с множеством повторяющихся элементов ожидаемое время выполнения стало .

• Формат ввода: Первая строка содержит целое число . В следующей строке содержится последовательность из целых чисел .
• Формат вывода: Вывод последовательности в неубывающем порядке.
• Ограничения: ; для всех .

Пример:

Ввод	Вывод
5 2 3 9 2 2	2 2 2 3 9

• Совет: не используйте встроенные алгоритмы сортировки.

Решение

Для ускорения RandomizedQuickSort мы разделим входной массив на три подмассива: элементы меньше опорного, равные ему и элементы больше. В более простом подходе достаточно сканировать массив трижды и собрать необходимые элементы.

✒️ Упражнение:
Продемонстрируйте, как разделить массив на три части (меньше опорного элемента m, равняется ему и больше него) на месте — без использования дополнительной памяти.