В этом параграфе вы разберёте, почему стандартная реализация быстрой сортировки может работать медленно на массивах с повторяющимися элементами. Вы узнаете, как изменить алгоритм, чтобы избежать деградации производительности, и научитесь реализовывать трёхчастное разбиение, которое делает сортировку устойчивой даже в сложных случаях.
Ключевые вопросы параграфа
- Почему стандартная быстрая сортировка может работать медленно на массивах с повторяющимися элементами?
- Как изменить алгоритм так, чтобы избежать деградации производительности?
- Как реализовать трёхчастное разбиение и почему оно даёт прирост в эффективности?
Псевдокод
1RandomizedQuickSort(c):
2 if |c| <= 1: # тут и сортировать нечего
3 return c
4 m = random_choice(c) # выбираем случайный элемент из массива
5 определяем элементы c_small меньшие m
6 определяем элементы c_large большие m
7 RandomizedQuickSort(c_small) # рекурсивный вызов алгоритма
8 RandomizedQuickSort(c_large)
9 объединяем c_small, m и c_large в итоговый массив c_sorted
10 return c_sorted
В этом псевдокоде подразумевается, что все элементы массива разные. Ожидаемое время выполнения алгоритма составляет .
Изменение массива
Алгоритм легко изменить для случая, когда в этом массиве есть повторы. Чтобы это сделать, пусть в содержатся все элементы со значением не более , а не элементы со значением менее . Тем не менее такая модификация становится медленной даже относительно ожидаемого времени выполнения. Например, если все элементы одинаковы, разделяется на две части: размер составляет , а в нет элементов. Так как это разделение требует от RandomizedQuickSort времени , общее время выполнения составляет:
то есть вместо .
Ваша цель — изменить описанный выше алгоритм RandomizedQuickSort так, чтобы даже при последовательностях с множеством повторяющихся элементов ожидаемое время выполнения стало .
- Формат ввода: Первая строка содержит целое число . В следующей строке содержится последовательность из целых чисел .
- Формат вывода: Вывод последовательности в неубывающем порядке.
- Ограничения: ; для всех .
Пример
|
Ввод |
Вывод |
|
5 |
2 2 2 3 9 |
Совет: не используйте встроенные алгоритмы сортировки.
Решение
Для ускорения RandomizedQuickSort мы разделим входной массив на три подмассива: элементы меньше опорного, равные ему и элементы больше. В более простом подходе достаточно сканировать массив трижды и собрать необходимые элементы.
Упражнение
Продемонстрируйте, как разделить массив на три части (меньше опорного элемента m, равняется ему и больше него) на месте— без использования дополнительной памяти.
Что дальше
Теперь вы умеете модифицировать быструю сортировку так, чтобы она оставалась эффективной даже при наличии большого числа одинаковых элементов. Вы освоили идею трёхчастного разбиения и поняли, как оно помогает избежать худших сценариев и ускорить работу алгоритма.
Далее — задача на подсчёт инверсий. Вы узнаете, как можно сочетать сортировку и рекурсию, чтобы вычислять количество нарушений порядка быстрее, чем простым перебором.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Стандартная быстрая сортировка может деградировать , если в данных много одинаковых значений.
- Модификация с трёхчастным разбиением (на меньше, равные и больше опорного) делает сортировку стабильной по времени.
- Случайный выбор опорного элемента помогает избежать худших случаев.
- Алгоритм остаётся простым, но работает существенно быстрее в практических задачах.