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
В этом псевдокоде подразумевается, что все элементы массива разные. Ожидаемое время выполнения алгоритма составляет $O(n \log n)$.
Алгоритм легко изменить для случая, когда в этом массиве есть повторы. Чтобы это сделать, пусть в $c_{small}$ содержатся все элементы со значением не более $m$, а не элементы со значением менее $m$. Тем не менее такая модификация становится медленной даже относительно ожидаемого времени выполнения. Например, если все элементы $c$ одинаковы, $c$ разделяется на две части: размер $c_{small}$ составляет $n-1$, а в $c_{{large}}$ нет элементов. Так как это разделение требует от RandomizedQuickSort
времени $a\cdot n$, общее время выполнения составляет: $$
a \cdot n+a \cdot (n-1)+a \cdot (n-2)+\dotsb = a \cdot \frac{n \cdot (n+1)}{2} ,
$$ то есть $O(n^2)$ вместо $O(n \log n)$.
Ваша цель — изменить описанный выше алгоритм RandomizedQuickSort
так, чтобы даже при последовательностях с множеством повторяющихся элементов ожидаемое время выполнения стало $O(n \log n)$.
- Формат ввода: Первая строка содержит целое число $n$. В следующей строке содержится последовательность из $n$ целых чисел $a_0, a_1, \dotsc, a_{n-1}$.
- Формат вывода: Вывод последовательности в неубывающем порядке.
- Ограничения: $1 \le n \le 10^5$; $1 \le a_i \le 10^9$ для всех $0 \le i < n$.
Пример:
Ввод | Вывод |
---|---|
5 2 3 9 2 2 | 2 2 2 3 9 |
- Совет: не используйте встроенные алгоритмы сортировки.
Решение
Для ускорения RandomizedQuickSort
мы разделим входной массив на три подмассива: элементы меньше опорного, равные ему и элементы больше. В более простом подходе достаточно сканировать массив трижды и собрать необходимые элементы.
✒️ Упражнение:
Продемонстрируйте, как разделить массив на три части (меньше опорного элемента m, равняется ему и больше него) на месте — без использования дополнительной памяти.