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

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

  1)

  Более подробную информацию о различных алгоритмах упорядочения смотрите в книге Дональда Кнута " Искусство программирования ЭВМ", том 3: "Сортировка и поиск".

  2)

  В названиях алгоритмов мы будем следовать Кнуту.

  3)

  Одно - при сдвиге и еще одно - при проверке необходимости сдвига

  4)

  Одно - при сдвиге и еще две - при переписывании вставляемого элемента.

  5)

  Напомним, что log N означает log2 N

  6)

  Если бы в строке {***} программы ПРВыб стоял знак строгого неравенства, то в качестве минимума была бы выбрана первая тройка. Однако очевидно, что выгоднее брать последний из совпадающих элементов: благодаря этому все они оказываются левее, чем тот превосходящий всех их элемент, с которым выбранный минимум меняется местами.

  7)

  Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание).

  8)

  Н. Вирт. Алгоритмы и структуры данных (любое издание).

  9)

  Д. Л. Шелл назвал ее "сортировкой вставками с убывающим шагом".

  10)

  Для других входных данных это число может быть значительно меньше или же еще больше.

  11)

  Грохот - техническое "сито".

  12)

  В оригинале QuickSort.

© 2003-2007 INTUIT.ru. Все права защищены.