Эффективность алгоритма Быстр
Реализация алгоритма Быстр
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.Алгоритм Быстрой сортировки имеет в среднем2) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).
Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.
|
|
|
1) См. Д. Кнут. Искусство программирования для ЭВМ, любое издание. Т.1 Основные алгоритмы.
2) Существует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1). Поэтому при описании эффективности мы использовали слова "в среднем".
10. Лекция: Адреса и указатели. Списочные структуры данных:
Основные понятия и применение динамически распределяемой памяти. Списочные структуры данных и принципы работы с ними.