Реферат: Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева
Лабораторная работа № 1Сравнить эффективность методов сортировки массивов:
Метод прямого выбора и метод сортировки с помощью дерева.
Сортировка с помощьюпрямого выбораЭтот прием основан на следующихпринципах:
1.Выбирается элемент с наименьшим ключом.
2.Он меняется местами с первым элементомai.
3.Затем этот процесс повторяется с оставшимися n-1элементами, n-2элементами и т.д. до тех пор,пока не останется один, самый большой элемент.
Процесс работы этим методом с темиже восемью ключами, что и в табл.2.1,приведен в табл.2.2. Алгоритмформулируется так:
FORi:=ITOn-1 DO
присвоитьkиндекснаименьшего изa[i],,,a[nJ; поменять местамиa[i] и a[j];
end
Такой метод– егоназывают прямымвыбором–в некотором смысле противоположен прямомувключению. При прямом включении на каждом шаге рассматриваются только один очередной элемент исходнойпоследовательности и все элементыготовой последовательности, среди которых отыскивается точка включения; припрямом выборе для поиска одного элементас наименьшим ключом просматриваются все элементы исходной последовательности инайденный помещается как очередной элемент в готовую последовательность.Полностью алгоритм прямого выбора приводится в прогр.2.3.
Таблица2.2. Пример сортировки с помощью прямого выбора
Начальные ключи
<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">44 55 12 42 94 18 06 67
<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">06 55 12 42 94 18 44 67
<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">06 12 55 42 94 18 44 67
<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">06 12 18 42 94 55 4467
<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">05 12 18 42 94 55 44 67
<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">05
<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">12 13 42 44 55 94 67<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">06 12 18 42 44 55 9467
<span Courier New"; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode: line">06
<span Courier New";mso-bidi-font-family:«Times New Roman»;layout-grid-mode: line;mso-no-proof:yes"> 12 18 42 44 55 67 94<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">PROCEDURE StraightSfcleclion;
VARi,j,k: index; x:item; BEGIN
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">FORi:=1TO n-1 DO k:= i; x
<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line;mso-no-proof:yes"> :=<span Courier New";mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US;layout-grid-mode:line"> a[i]; FORj:=i+1TO n DO <span Courier New";mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line; mso-no-proof:yes"><span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">IF a[j]<xTHENk:=j;X:= a[k] END BND;
<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line">а<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line">[k]:=а[i];<span Courier New";mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US;layout-grid-mode:line"> a[i]<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line;mso-no-proof:yes"> ; =<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line"> x END ENDStraightSelectionПрогр.2.3.Сортировка с помощью прямого выбора,
Анализ прямого выбора.Число сравнений ключей (С), очевидно, не зависитот начального порядка ключей. Можно сказать, что в этом смысле поведение этогометода менее естественно, чем поведение прямого включения. Для С имеем
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;layout-grid-mode: line">с=(n
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode: line">2<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">-<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line"> n)/2Число перестановокминимально Mmin=3*(n-l) (2.6)
в случае изначально упорядоченных ключей и максимально
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line">Mmax
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line"> =n2/4 +3(n-1)если первоначально ключи располагались в обратном порядке. Для того чтобыопределитьMavg,мы должны рассуждать так. Алгоритм просматриваетмассив, сравнивая каждый элемент с только что обнаруженной минимальнойвеличиной; если он меньше первого, то выполняется некоторое присваивание.Вероятность, что второй элемент окажется меньше первого, равна1/2, с этой же вероятностью происходят присваивания минимуму. Вероятность, что третий элементокажется меньше первых двух, равна1/3, авероятность для четвертого оказаться наименьшим— 1/4 и т. д.Поэтому полное ожидаемое число пересылок равно Нn—1, где Нn — n-егармоническое число:
Нn=1+1/2+1/3+...+1/nНпможно выразить и так: Нп=Inn+g+1/2n— 1/12n2 + ...
гдеg=0.577216… —константа Эйлера. Длядостаточно больших n мы можем игнорировать дробныесоставляющие и поэтому аппроксимировать среднее число присваиванийнаi-мпросмотре выражением
Fi-lni+g+l
Среднее число пересылокMavg всортировке с выбором есть суммаFiсiот1 до n:
Mavg=n*(g+l)+(Si: 1<i<n; lni)
Вновь аппроксимируя этусумму дискретных членов интегралом Integral(1:п)ln x dx==x*(ln x—1) ==n*ln(п)—n+I
получаем, наконец,приблизительное значение Mavg=n(ln (n)+g)
Отсюда можно сделать заключение, что, как правило, алгоритм с прямымвыбором предпочтительнее строгого включения. Однако, если ключи в начале упорядоченыили почти упорядочены, прямое включение будет оставаться несколько более быстрым.
2.3.2.Сортировка с помощью дереваМетод сортировки с помощью прямого выбора основанна повторяющихся поисках наименьшего ключа среди nэлементов, среди оставшихся n—1 элементов и т. д. Обнаружениенаименьшего среди п элементов требует—это очевидно —n — 1 сравнения, среди n — 1 уже нужно n — 2 сравнений и т.д. Сумма первых n — 1целых равна 1/2*(n2 — n). Как же в таком случае можно усовершенствоватьупомянутый метод сортировки? Этого можно добиться, только оставляя послекаждого прохода больше информации, чем просто идентификация единственногоминимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключейменьший. С помощью n/4сравнений — меньший из пары уже выбранныхменьших и т. д. Проделав n— 1 сравнений, мы можем построить дерево выбора вроде представленногона рис.2,3 и идентифицировать его коренькак нужный нам наименьший ключ[2.21.
Второй этап сортировки — спусквдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путемзамены либо на пустой элемент (дырку) в самом низу,либо на элемент из соседней ветви в промежуточных вершинах (см. рис.2.4 и2.5). Элемент,передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым)ключом, и его можно исключить. После п таких шаговдерево станет пустым (т. е. в нем останутся только дырки), и процесс сортировкизаканчивается. Обратите внимание — на каждомиз nшагов выбора требуетсятолько lognсравнений. Поэтому на весь процесс понадобится порядкаn*lognэлементарных операций плюс еще n шагов на построение дерева. Это весьма существенноеулучшение не только прямого метода, требующего п2 шагов, но и даже метода Шелла,где нужно п^1.2 шага. Естественно,сохранение дополнительной информации делает задачу более изощренной, поэтому всортировке по дереву каждый отдельный шаг усложняется. Ведь в конце концов длясохранения избыточной информации, получаемой при начальном проходе, создается некоторая древообразная структура.Наша следующая задача— найти приемыэффективной организации этой информации.
Конечно, хотелось бы, в частности, избавиться от дырок, которыми вконечном итоге будет заполнено все дерево и которые порождают много ненужныхсравнений. Кроме того, надо было бы поискать такоепредставление дерева из пэлементов, которое требует лишь пединиц памяти, а не 2n—1, как это былораньше. Этих целей действительно удалось добиться вметодеHeapsort<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-fareast-language: RU;mso-bidi-language:AR-SA;layout-grid-mode:line">[1]*)
изобретенномД. Уилльямсом(2.14),где было получено, очевидно, существенное улучшение традиционных сортировок спомощью деревьев. Пирамида определяется как последовательность ключейhi., hL+1,..,hr,такая, что<img src="/cache/referats/1358/image002.gif" v:shapes="_x0000_i1025">
Если любое двоичное дерево рассматривать как массив по схеме на рис.2.6, то можно говорить, что деревьясортировок на рис.2.7 и2.8 суть пирамиды, а элементh1,в частности, их наименьший элемент: hi==min(hi,h2,...,hn).Предположим, есть некоторая пирамида сзаданными элементамиhL+1,...,hRдля некоторых значенийL иRи нужнодобавить новый элемент х, образуя расширенную пирамидуhi.,.. . ...,liR.Возьмем, например, в качестве исходной пирамидуhi,...,hr,показанную на рис.2.7, и добавим к ней слева элементh1==44<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»;mso-ansi-language: EN-US;mso-fareast-language:RU;mso-bidi-language:AR-SA;layout-grid-mode:line">[2]
Новая пирамида получается так: сначала х ставится наверх древовидной структуры, а затем онпостепенно опускается вниз каждый раз по направлению наименьшего из двухпримыкающих к нему элементов, а сам этот элемент передвигается вверх. Вприведенном примере значение44 сначаламеняется местами с06, затем с12 ц в результатеобразуется дерево, представленное на рис.2.8.Теперь мы сформулируем этот сдвигающий алгоритм так:i,j—пара индексов, фиксирующих элементы, меняющиеся на каждом шаге местами.Читателю остается лишь убедиться самому, что предложенный метод сдвиговдействительно сохраняет неизменным условия(2.13), определяющие пирамиду.Р.Флойдомбыл предложен некий «лаконичный»способ построения пирамиды «на том же месте». Его процедура сдвига представленакак прогр.2.7. Здесь hi. ..hn —некий массив, причем Ьщ...hn (пп= ==(nDIV2)+1)уже образуют пирамиду, поскольку индексовi, j,удовлетворяющих отношениямj =2i (илиj = 2i+1), просто несуществует. Эти элементы образуют как бы нижний слой соответствующего двоичногодерева (см. рис.2.6), для них никакой
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">P
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">ROCEDUREsift(L, R; index);<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">VAR i, j:index; x: item;
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">B
<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line">EGINi<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">:<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line"> = L; J<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">:<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line;mso-no-proof:yes">=<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line"> 2*L;<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">x :=<span Courier New";mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US; layout-grid-mode:line"> a[L];<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">IF (j
<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes"><<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line"> R)<span Courier New"; mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">&<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line"> (a[J+l]<span Courier New";mso-bidi-font-family:«Times New Roman»;layout-grid-mode:line; mso-no-proof:yes"> <<span Courier New";mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US; layout-grid-mode:line"> a[j] THEN j<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line;mso-no-proof:yes">:=<span Courier New"; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode: line">j+l<span Courier New";mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;layout-grid-mode:line"> END<span Courier New";mso-bidi-font-family: «Times New Roman»;layout-grid-mode:line;mso-no-proof:yes">;<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">WHILE
<span Courier New";mso-bidi-font-family:«Times New Roman»; layout-grid-mode:line;mso-no-proof:yes"> (j <<span Courier New";mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US; layout-grid-mode:line"> =R)&(a[j]<x) DO<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">a[i]:= a[j]: i:=j; i:= 2*j;
<span Courier New"; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode: line">IF
<span Courier New"; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode: line">(j<R)&(a[j+1]<a[j]) THEN j:=j+1 END<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">END
<span Courier New";mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;layout-grid-mode:line">END sift
Прогр.2.7.Sift.
упорядоченности не требуется. Теперь пирамида расширяется влево; каждыйраз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Табл.2.6 иллюстрирует весь этот процесс, а получающаясяпирамида показана на рис.2.6.
Следовательно, процесс формирования пирамиды из пэлементовhi...hnна том же самом месте описывается так:
L :==(n DIV2) + 1;
WHILE L>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+lEND; WHILE(j<=R)&(x<a[j])DO a[i]:=a[j]; i :=j: j:=2*j: IF(J<R)&(a[i]<a[j+l]) THENj:=j+1 END END ENDsift;
BEGIN L:=:(nDIV2)+l:R:=n; WHILE L>1 DO L:=L-l;sift(L,R) END; WHILER>1DO x :=a[l]; a[l]:=a[R]; a[R]:=x; R:=R-l; sifl(L, R) END ENDHeapSort
Прогр.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), причем отклонения от этого значенияотносительно невелики.
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">[1]
Здесьмы оставляем попытки перевести названия соответствующих методов на русскийязык, ибо ни уже не более чем собственные имена, хотя в названиях первыхупоминавшихся методов еще фигурировал некоторый элемент описания сути самогоприема сортировки.— Прим. перев.<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">[2]
Этонесколько противоречит утверждению, чтоlu+i..) ...hr—пирамида, но надеемся, сам читатель разберется, Что хотел сказать автор.— Прим.перев.