SUBROUTINE HEAP UiHiHl

. ПОДПРОГРАММА ПОМЕЩАЕТ. ЭЛЕМЕНТ A{j) Б ПИРАМИДУ ИЗ 11,ЕЛЫХ ЧИСЕЛ А(1), Аг), . . . , A(N).

INTEGER A(N)iTEHP

СПОМЕЩАЕМ AW в пирамиду)

" L 5 К+1 LOG N

IF <L .LC. W .AND. lAIJ) .LT. AIK) .OR. AlJ) .LT. "(LJ)) COTO £00 UOS N. LOS N «Х

GOTO SOO 1

ТОГДА (ОБМЕН С АШ.

ego IF <A(K) .ОТ. n(Ll) GOTO 300

GOTO 100

THEN

300 TEMP = Д1Л

A(JI = A(KI J = К

*(K1 = TEMP GOTO 100

ELSE

«00 TEMP = A(J)

A(JI = A(LI A (LI s TEMP

J = L

«ОТО 100

ELSE (IS I*J .ta. N)

SOO IF <K .EO. N .AMD. A(J1 .IT, *(K)) 60T0 600 GOTO 700

LOe N i A

»oa

7.00 RETURN END

THEN

TEMP s A(J> A(J) = A(NI A(N) = TEMP

Рис. 5.1.9. Реализация на Фортране алгоритма НЕ.АР,

SUBROUTINE HPSORT (AiN)

ПОДПРОГРАММА Cheapeort) сортирует иассмв

ЦЕЛЫХ ЧИСЕЛ А№, AU)= А(3),. . . , A(.N), С ИСПОЛЬЗОВАЯИЕМ АЛГОРИТМА дж. ВИЛЬЯМСА.ССАСМ 7(1964), 347-346).

INTEGER ACNl.TEHP

(ИНИилАЛИЗАЩ1Я I, М)

1 = ы/z

L = I М а N

(ПОСТРОЕНИЕ ПИРАМИДЫ)

DO iOO К = 1.L

CALLHEAP (Г.А.Н} 1 = 1-1

aoD CONTINUE

(сортировка)

во- гоо.к = -г.м Temp = ац)

й(1) = А(Н1 А(М). = ТЕМР М = И-1

CALL HEAP (liA.H) SOO CONTINUE-RETURN

R-l N-l N-l. N-l

(N-i)*H2

Рис. 5.1.10. Реализация на Фортране алгоритма HEAPSORT.

Обсудив средние оценки эффективности алгоритмов SIS, QUICKSORT и HEAPSORT, проведем некоторое простое тестирование для проверки нашего анализа. Для каждой из трех разных выборок (Л/=100, 200, 500) мы образуем 50 различных множеств из N случайных целых чисел и затем отсортируем каждое множество, применив все три алгоритма. Зафиксируем среднее число перестановок и сравнений, выполненных для каждого из трех алгоритмов и трех значений N. Тогда экспериментальные кривые, вид которых предсказан теорией, будут поставлены в соответствие данным.

Ключи для тестовых данных были получены с помощью датчика случайных чисел с равномерным распределением в области целочисленных значений от 1 до 100 ООО. Размер выборки 50 множеств для каждого значения N был экспериментально определен по тому же эмпирическому правилу, которое использовалось для проверки алгоритма PRIM в гл. 4.

Мы интересуемся как числом сравнений, так и числом перестановок, произведенных каждым алгоритмом. Сравнение осуществляется оператором типа: if Л(/)<Л(/) или if В<Л(/). Перестановка состоит из набора трех операторов присваивания, таких, как

ТЛ(/) Л(/)Л(/) A{J)T.

Однако в алгоритме SIS перестановка происходит несколько иначе; во-первых, выбирается величина для сравнения В -<- Л (/), что считается одной третью перестановки. Затем выполняется присваивание Л (7+1)Л (7), также представляющее треть перестановки. Наконец, при помощи оператора типа Л (/)-<- В заменяется начальное значение - еще одна треть перестановки.

Средние значения, полученные в этих местах для каждого значения N и каждого алгоритма, сведены в табличку. Мы будем анализировать только число сравнений для алгоритма QUICKSORT; остальные данные обрабатьшаются аналогично и оставлены для интересующегося читателя. Результаты проверки сложности алгоритмов S1S, QUICKSORT и HEAPSORT

Поскольку наш анализ сложности показал, что QUICKSORT имеет среднюю оценку трудоемкости порядка ONlogN), было бы разумным попытаться подогнать к данным кривую вида

fQiN)=Cimog2N+C2N+Cs.

Рассмотрим пока только главный член CiN\og2N. Подгоним (несколько произвольно) главный член к данным при N=100 и 500, используем среднее этих двух значений Ci для предсказания среднего числа сравнений для N=200 и затем сравним предсказание с наблюдением (см. упр. 4.2.6 по интерполяции и экстраполяции).

Для "=100 находим, что Ci 100Iog2l00=712, или Ci«l,07. Для дг=500 имеем, что Ci500 log2500=5102, или Cil.M. Это дает среднее значение

С=1Ц1 = Ц1 = 1Л05,

на основании чего для N=200 предсказываем 1.105(200) (log2200)«:! «;1б90 .сравнений; полученное экспериментальное значение равно 1682. Хотя фактическое отсутствие ошибки отчасти случайно, этот простой анализ оказывает значительную поддержку теории.

Нижние границы при сортировке сравнениями

Если оценивать алгоритмы сортировки, которые мы до сих пор рассматривали, то трудоемкость алгоритма SIS в худшем случае имеет порядок 0{N) и средняя трудоемкость - тоже порядка 0{N). Средняя трудоемкость алгоритма QUICKSORT - порядка 0{NlogN), и трудоемкость алгоритма HEAPSORT в худшем случае - порядка 0{NlogN). Естественно поинтересоваться, возможно ли разработать алгоритм сортировки, средняя трудоемкость или трудоемкость в худшем случае которого была бы меньше, чем O(NlogN). К сожалению, такого алгоритма не существует. Можно доказать, что для любого алгоритма, который работает путем сравнения пар элементов, средняя трудоемкость и трудоемкость в худшем случае имеют порядок по меньшей мере O(NlogN).

Во-первых, заметим, что любой алгоритм для сортировки элементов сравнениями может быть представлен Л/-элементным деревом решений, как показано на рис. 5.1.11. Каждая внутренняя вершина дерева решений представляет сравнение (или решение), сделанное алгоритмом в некотором месте во время его выполнения. Ребра, выходящие вниз из вершины, представляют два возможных результата сравнения. Конечные вершины дерева решений представляют отсортированные последовательности, получаемые алгоритмом. Поскольку любая из N\ перестановок N произвольных элементов Oi, Ог, . . ., Ojv является возможным результатом работы сортирующего алгоритма,

- элементное дерево решений каждого алгоритма сортировки сравнениями должно иметь по крайней мере N1 конечных вершин.