Быстрая сортировка

Эффективность алгоритма УлПир

Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.

В среднем этот алгоритм имеет сложность, пропорциональную N*log N.

Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка¹²⁾. Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).

¹⁾ Более подробную информацию о различных алгоритмах упорядочения смотрите в книге Дональда Кнута " Искусство программирования ЭВМ", том 3: "Сортировка и поиск".
²⁾ В названиях алгоритмов мы будем следовать Кнуту.
³⁾ Одно - при сдвиге и еще одно - при проверке необходимости сдвига
⁴⁾ Одно - при сдвиге и еще две - при переписывании вставляемого элемента.
⁵⁾ Напомним, что log N означает log₂ N
⁶⁾ Если бы в строке {***} программы ПРВыб стоял знак строгого неравенства, то в качестве минимума была бы выбрана первая тройка. Однако очевидно, что выгоднее брать последний из совпадающих элементов: благодаря этому все они оказываются левее, чем тот превосходящий всех их элемент, с которым выбранный минимум меняется местами.
⁷⁾ Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание).
⁸⁾ Н. Вирт. Алгоритмы и структуры данных (любое издание).
⁹⁾ Д. Л. Шелл назвал ее "сортировкой вставками с убывающим шагом".
¹⁰⁾ Для других входных данных это число может быть значительно меньше или же еще больше.
¹¹⁾ Грохот - техническое "сито".
¹²⁾ В оригинале QuickSort.

5. Лекция: Символы и строки. Множества:
Приемы работы с символьными и строковыми данными. Использование множеств. Задание больших множеств массивами.