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

Лабораторная работа № 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. Пример сортировки с помощью прямого выбора

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

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 4467

05 12 18 42 94 55 44 67

05

12 13 42 44 55 94 67

06 12 18 42 44 55 9467

06

12 18 42 44 55 67 94

PROCEDURE StraightSfcleclion;

VARi,j,k: index; x:item; BEGIN

FORi:=1TO n-1 DO k:= i; x

:= a[i]; FORj:=i+1TO n DO

IF a[j]<xTHENk:=j;X:= a[k] END BND;

а[k]:=а[i]; a[i] ; = x END ENDStraightSelection

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

Анализ прямого выбора.Число сравнений ключей (С), очевидно, не зависитот начального порядка ключей. Можно сказать, что в этом смысле поведение этогометода менее естественно, чем поведение прямого включения. Для С имеем

с=(n

2- n)/2

Число перестановокминимально Mmin=3*(n-l) (2.6)

в случае изначально упорядоченных ключей и максимально

Mmax

=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[1]*)

изобретенномД. Уилльямсом(2.14),где было получено, очевидно, существенное улучшение традиционных сортировок спомощью деревьев. Пирамида определяется как последовательность ключейhi., hL+1,..,hr,такая, что

Если любое двоичное дерево рассматривать как массив по схеме на рис.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[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), для них никакой

P

ROCEDUREsift(L, R; index);

VAR i, j:index; x: item;

B

EGINi: = L; J:= 2*L;x := a[L];

IF (j

< R)& (a[J+l] < a[j] THEN j:=j+l END;

WHILE

(j < =R)&(a[j]<x) DO

a[i]:= a[j]: i:=j; i:= 2*j;

IF

(j<R)&(a[j+1]<a[j]) THEN j:=j+1 END

END

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, Построение пирамиды

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

чае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), причем отклонения от этого значенияотносительно невелики.

[1]

Здесьмы оставляем попытки перевести названия соответствующих методов на русскийязык, ибо ни уже не более чем собственные имена, хотя в названиях первыхупоминавшихся методов еще фигурировал некоторый элемент описания сути самогоприема сортировки.— Прим. перев.

[2]

Этонесколько противоречит утверждению, чтоlu+i..) ...hr—пирамида, но надеемся, сам читатель разберется, Что хотел сказать автор.— Прим.перев.

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Программирование на "Си"

29 Августа 2013

Реферат по программированию, базе данных

Игра на ловкость "Змейка"

29 Августа 2013

Реферат по программированию, базе данных

Программирование на "СИ" (ТХТ, СИ)

29 Августа 2013

Реферат по программированию, базе данных

Лабораторные работы по теории и технологии информационных процессов

29 Августа 2013