Программирование на языке Pascal



         

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


Алгоритм Быстрой сортировки имеет в среднем2) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).

Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.

  1)

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

  2)

  Существует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1). Поэтому при описании эффективности мы использовали слова "в среднем".

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




Содержание  Назад