Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева

Лабораторная работа № 1

Сравнить эффективность методов сортировки массивов:

Метод прямого выбора и метод сортировки с помощью дерева.

Сортировка с помощью прямого выбора

Этот прием основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом ai.

3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2

элементами и т.д. до тех пор, пока не останется один, самый большой

элемент.

Процесс работы этим методом с теми же восемью ключами, что и в табл. 2.1,

приведен в табл. 2.2. Алгоритм формулируется так:

FORi:=ITO n-1 DO

присвоить k индекс наименьшего из a[i],,, a[nJ; поменять местами a[i] и

a[j];

end

Такой метод – его называют прямым выбором – в некотором смысле

противоположен прямому включению. При прямом включении на каждом шаге

рассматриваются только один очередной элемент исходной последовательности и

все элементы готовой последовательности, среди которых отыскивается точка

включения; при прямом выборе для поиска одного элемента с наименьшим ключом

просматриваются все элементы исходной последовательности и найденный

помещается как очередной элемент в готовую последовательность. Полностью

алгоритм прямого выбора приводится в прогр. 2.3.

Таблица 2.2. Пример сортировки с помощью прямого выбора

Начальные ключи

44 55 12 42 94 18 06 67

06 55 12 42 94 18 44 67

06 12 55 42 94 18 44 67

06 12 18 42 94 55 44 67

05 12 18 42 94 55 44 67

05 12 13 42 44 55 94 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

PROCEDURE StraightSfcleclion;

VAR i,j,k: index; x: item; BEGIN

FORi:=1 TO n-1 DO k:= i; x := a[i]; FORj:= i+1TO n DO

IF a[j] 1 DO L :== L — 1; sift(L, n) END

Для того чтобы получить не только частичную, но и полную упорядоченность

среди элементов, нужно проделать n сдвигающих шагов, причем после каждого

шага на вершину дерева выталкивается очередной (наименьший) элемент. И

вновь возникает вопрос: где хранить «всплывающие» верхние элементы и можно

ли или нельзя проводить обращение на том же месте? Существует, конечно,

такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это

будет х), прятать верхний элемент пирамиды в освободившемся теперь месте, а

х сдвигать в нужное место. В табл. 2.7 приведены необходимые в этом слу-

.Таблица 2.6, Построение пирамиды

|44 |55 |12 |42 |94 |18 |06 |67 |

|44 |55 |12 |42 |94 |18 |06 |67 |

|44 |55 |06 |42 |94 |18 |12 |67 |

|44 |42 |06 |55 |94 |18 |12 |67 |

|06 |42 |12 |55 |94 |18 |44 |67 |

Таблица 2.7. Пример процесса сортировки с помощью Heapsort

|06 |42 |12 |55 |94 |18 |44 |67 |

|12 |42 |18 |55 |94 |67 |44 |06 |

|18 |42 |44 |55 |94 |67 |12 |06 |

|42 |55 |44 |67 |94 |18 |12 |06 |

|44 |55 |94 |67 |42 |18 |12 |06 |

|55 |67 |94 |44 |42 |18 |12 |06 |

|67 |94 |55 |44 |42 |18 |12 |06 |

|94 |67 |55 |44 |42 |18 |12 |06 |

чае n — 1 шагов. Сам процесс описывается с помощью процедуры sift (прогр.

2.7) таким образом:

R:=n; WHILE R>1 DO х := а[l]; a[l] := a[R]; a[R] := x: R:=R-l; sift(l,R)

END

Пример из табл. 2.7 показывает, что получающийся порядок фактически

является обратным. Однако это можно легко исправить, изменив направление

«упорядочивающего отношения» в процедуре sift. В конце концов получаем

процедуру Heapsort (прогр. 2.8),

PROCEDURE HeapSort; VAR L, R: index; х: item; PROCHDURE sift(L, R: index);

VAR i,j:index; x: item; BEGIN i: = L; j := 2*L: x := a[L]; IF(j < R) &

(a[j] < a[j+1]) THEN j := j+l END; WHILE(j 1 DO L: = L-l; sift(L, R) END; WHILER>1

DO x := a[l]; a[l] := a[R]; a[R] := x; R := R-l; sifl(L, R) END END

HeapSort

Прогр. 2.8. HeapsorL

Анализ Heapsort. На первый взгляд вовсе не очевидно, что такой метод

сортировки дает хорошие результаты. Ведь в конце концов большие элементы,

прежде чем попадут на свое место в правой части, сначала сдвигаются влево.

И действительно, процедуру не рекомендуется применять для небольшого, вроде

нашего примера, числа элементов. Для больших же n Heapsort очень

эффективна; чем больше п, тем лучше она работает. Она даже становится

сравнимой с сортировкой Шелла.

В худшем случае нужно п/2 сдвигающих шагов, они сдвигают элементы на log

(n/2), log (п/2—1), ... ..., log(n—l) позиций (логарифм (по основанию 2)]

«обрубается» до следующего меньшего целого). Следовательно, фаза сортировки

требует n—1 сдвигов с самое большое log(n—1), log(n—2), ..., 1

перемещениями. Кроме того, нужно еще n —1 перемещений для просачивания

сдвинутого элемента на некоторое расстояние вправо. Эти соображения

показывают, что даже в самом плохом из возможных случаев Heap-sort

потребует n*log n шагов. Великолепная производительность в таких плохих

случаях—одно из привлекательных свойств Heapsort.

Совсем не ясно, когда следует ожидать наихудшей (или наилучшей)

производительности. Но вообще-то кажется, что Heapsort «любит» начальные

последовательности, в которых элементы более или менее отсортированы в

обратном порядке. Поэтому ее поведение несколько неестественно. Если мы

имеем дело с обратным порядком, то фаза порождения пирамиды не требует

каких-либо перемещений. Среднее число перемещений приблизительно равно п/2*

log(n), причем отклонения от этого значения относительно невелики.

-----------------------

[1] Здесь мы оставляем попытки перевести названия соответствующих методов

на русский язык, ибо ни уже не более чем собственные имена, хотя в

названиях первых упоминавшихся методов еще фигурировал некоторый элемент

описания сути самого приема сортировки. — Прим. перев.

[2] Это несколько противоречит утверждению, что lu+i ..) ...hr—пирамида, но

надеемся, сам читатель разберется, Что хотел сказать автор. — Прим. перев.