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

Реализация алгоритма Быстр

type index = 1..N;var a: array[index] of integer; procedure quicksort(l,r:index); var i,j: index; x,z: integer; begin i:= l; j:= r; x:= a[(l+r)div 2]; repeat while a[i]< x do inc(i); while a[j]> x do dec(j); if i <= j then begin z:= a[i]; a[i]:= a[j]; a[j]:= z; inc(i); dec(j); end; until i>j; if l<j then quicksort(l,j); if i<r then quicksort(i,r); end;begin {тело программы}... quicksort(1,n);...end.

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

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

¹⁾ См. Д. Кнут. Искусство программирования для ЭВМ, любое издание. Т.1 Основные алгоритмы.
²⁾ Существует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N². Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1). Поэтому при описании эффективности мы использовали слова "в среднем".

10. Лекция: Адреса и указатели. Списочные структуры данных:
Основные понятия и применение динамически распределяемой памяти. Списочные структуры данных и принципы работы с ними.

Дата добавления: 2014-01-03