Простые алгоритмы сортировки массива

Простые алгоритмы сортировки массива

Как было отмечено в разделе 1, в методах сортировки массива мы будем воспользоваться только одной “вспомогательной” переменной типа Элемент. Эта переменная употребляется для обмена 2-ух частей мас­сива. Так как обмен неких 2-ух частей массива неоднократно употребляется во всех методах сортировки, оформим этот маленький подалгоритм в виде процедуры:

procedure Обмен (I,J: word Простые алгоритмы сортировки массива);

var Эл: Элемент;

begin

Эл:=Массив[J];

Массив^] :=Массив[!] ;

Массив[I]:=Эл;

end;

Время от времени будем воспользоваться модификацией этого метода: поменять элементы только тогда, когда ключ (Ключ) первого параметра больше ключа второго. В программках будет употребляться итог рабо­ты этого метода – т.е. вправду ли мы поменяли Простые алгоритмы сортировки массива элементы ме­стами, – потому оформим этот подалгоритм в виде таковой логической функции:

function Упорядочили (I, J: word): boolean;


begin

if Массив[I].Ключ>Массив[J].Ключ

then begin Обмен(I,J); Упорядочили:=true; end

else Упорядочили:=false;

end;

Комфортно выделить в качестве подалгоритма и повторяющийся сдвиг нескольких частей массива (ср. с процедурой Обмен):

procedure Простые алгоритмы сортировки массива Сдвиг (I,J: word);

{Циклический сдвиг частей:

или I -> I+1 -> I+2 ->...-> J-1 -> J (при I

или I -> I-1 -> I-2 ->...-> J+1 -> J (при I>J).

}

var Эл: Элемент;

K: word;

begin

Эл:=Массив[J];

if J>I

then for K:=J downto I+1 do Массив[K]:=МассивК-1]

else for K:=J to Простые алгоритмы сортировки массива I-1 do Массив[K]:=МассивК+1];

Массив[I]:=Эл;

end;

Рассмотренную ранее функцию обмена 2-ух частей массива можно было бы также написать как личный случай метода Сдвиг, - но это, по-видимому, нерационально. Отметим также, что мы только один раз - а конкретно, при написании процедуры Сдвиг - выясняем, какой из наших Простые алгоритмы сортировки массива 2-ух частей (I-й либо J-й) имеет наименьший номер. В даль­нейшем же, т.е. при применении процедуры Сдвиг, мы будем хлопотать только о том, чтоб направление от первого из номеров-параметров ко второму было конкретно направлением сдвига.

Ниже, при печати текстов программ сортировки, мы не Простые алгоритмы сортировки массива будем специ­ально отмечать то, что описания приведённых трёх алгоритмов обмена и сдвига - Обмен, Упорядочили и Сдвиг - всегда опущены. Отметим, что если несколько разных процедур сортировки собраны в единый мо­дуль, то три упомянутых подалгоритма должны оформляться “вровень” с остальными - т.е. быть доступными для всех других процедур[8].

4.1 Способ прямого включения

Неформально метод Простые алгоритмы сортировки массива этого способа (итерационный процесс) описыва­ется последующим образом: в процессе работы метода все элементы де­лятся на уже отсортированную часть, находящуюся сначала массива и ещё не отсортированную, находящуюся в конце. База итерационно­го процесса: можно считать, что сначала работы эта граница находится меж первым и вторым элементами Простые алгоритмы сортировки массива (т. к. массив из 1-го элемента все­гда является отсортированным). Шаг процесса: выбирается 1-ый эле­мент 2-ой части и переносится на нужное место в первой части; при всем этом граница меж частями массива двигается на один элемент.

Продемонстрируем метод на примере. Будем тут и везде ниже на рисунках, поясняющих способ Простые алгоритмы сортировки массива, изображать только ключи частей (т.е. поля Ключ переменных типа Элемент). Не считая этого, предполагаем, что в нарисованных горизонтально массивах 1-ый элемент находится слева, последний – справа, а в нарисованных вертикально – 1-ый элемент является верхним. Конфигурации массива показаны тут сверху вниз, граница меж частями массива – толстая линия, рассматриваемый Простые алгоритмы сортировки массива элемент выделен шрифтом большего размера, место в первой части, куда происходит включение - стрелкой.


Как мы лицезреем, граница меж частями массива “уехала” за границу массива - на этом сортировка кончается.

Программка для способа прямого включения несложна, отметим только внедрение в ней 2-ух ранее рассмотренных подалгоритмов – дихото­мии (при использовании заместо неё линейного поиска Простые алгоритмы сортировки массива [9] эффективность была бы ещё ниже), также сдвига.

procedure ПрямоеВключение (Граница: word); var I,J: word;

Куда: word;

begin

for I:=2 to Граница do begin

Куда:=Дихотомия(I-1,Массив[I].Ключ);

{дихотомией отыскали,

куда переписать рассматриваемый элемент

}

if Куда>0 then Сдвиг(Куда,I);

{ "else" рассматриваемый элемент не нужно

переписывать

}

end;

end;

Оценим эффективность Простые алгоритмы сортировки массива «в худшем» способа прямого включения. Ко­личество сравнений дихотомии мы оценивали ранее - данная величина для массива из n частей имеет порядок logn. Мы применяем дихотомию n-1 раз, причём для i-го внедрения массив состоит из i частей, потому общее число сравнений есть

Для подсчёта большего вероятного числа пересылок заметим, что на

i-м Простые алгоритмы сортировки массива шаге в худшем случае (а конкретно - когда рассматриваемый элемент пересылается в 1-ю позицию) будет i+1 пересылка, т.е. их общее число не превосходит

Из последнего заключаем, что для способа прямого включения эффективность “в худшем” есть n2 .

4.2 Способы прямого выбора

Общее во всех способах прямого выбора - то, что на каждом Простые алгоритмы сортировки массива шаге алго­ритмов посреди непросмотренной части массива выбирается малый (либо наибольший) элемент и переносится на 1-ое (последнее) воз­можное место.

Первым разглядим способ пузырька, нареченный так из-за аналогии со всплывающим пузырьком газа в воде.[10] Метод: на i-м шаге посреди непросмотренных частей (их n-i+1) выбирается малый, записывается на i Простые алгоритмы сортировки массива-е место массива, при всем этом промежные элементы сдвигаются (выплыл пузырёк):

При внимательном рассмотрении рисунка (либо процедуры сортиров­ки, составленной на базе описанного метода [11])

procedure Пузырек (Граница: word);

{==========}

function Минимум (Левый: word): word;

var I,Num,Key: word;

begin

Num:=Левый; Key:=Массив[Левый].Ключ;

{предполагаемый минимум}

for !:=Левый+1 to Простые алгоритмы сортировки массива Граница do

if Массив[I].Ключ then begin

Num:=I; Key:=Массив[I].Ключ;

{новый предполагаемый минимум}

end;

Min:=M;

end;

{==========}

var I: word;

begin

for I:=1 to Граница-1 do Сдвиг^МинимумЦ));

end;

становится непонятным применение подалгоритма Сдвиг: ведь у нас ещё нет никакой инфы об относительных значениях частей с но Простые алгоритмы сортировки массива­мерами от I+1 до Минимум(I). Потому подалгоритм Сдвиг можно заме­нить на более резвый Обмен, при всем этом процедура сортировки становит­ся такой[12]:

procedure ПузырекМ (Граница: word);

var I: word;

begin

for I:=1 to Граница-1 do Обмен(I,Минимум(I));

end;

Вот соответственный этой процедуре набросок:

Эффективность способа пузырька посчитаем Простые алгоритмы сортировки массива для последнего вариан­та. Незначительно переформулируем ранее отмеченный факт: перед i-м шагом метода у нас ещё нет никакой инфы об относительных зна­чениях частей с номерами от i до n. Из этого можно сделать такое заключение: на i-м шаге, вообщем говоря, нельзя отыскать малый элемент Простые алгоритмы сортировки массива, не сделав n-i сравнений. Таким макаром, в худшем случае общее число сравнений пропорционально

При подсчёте общего числа пересылок естественно учесть не только лишь те из их, которые вызываются подпрограммой Обмен, да и нужные для работы функции Минимум[13]. На любом шаге вероятны 3 пересыл­ки «первого рода», а очень вероятное число пересылок «второго Простые алгоритмы сортировки массива рода» находится в зависимости от номера шага метода: на i-м шаге их число равно 2*(n—i+1). Таким макаром, для всего метода очень воз­можное число пересылок есть

т. е. и для способа пузырька мы получаем такую же оценку эффективности: n2 .

Дальше разглядим один из вариантов т. н. шейкерной сортировки Простые алгоритмы сортировки массива, также являющейся развитием способа пузырька[14]. Поначалу отметим сле­дующий факт: во всех рассмотренных ранее методах вероятны си­туации, когда наш массив оказался отсортированным до окончания ра­боты метода. Интуитивно ясно, что неоднократные проверки таковой ситуации (для преждевременного окончания работы алгоритмов в случае её обнаружения) приведёт к существенному понижению Простые алгоритмы сортировки массива эффективности. Но вероятны ситуации, когда заблаговременно понятно, что входной массив «почти отсортирован» [15]. Разглядим два примера.

Во-1-х, применяя способ пузырька к такому массиву:

33 11 51 64 17 83 90 32

увидим, что три «пузырька» - 11, 17 и 32 - на сто процентов отсортируют массив. Но массив

90 11 17 32 33 51 64 83,

который тем паче охото именовать «почти отсортированным» - требу­ет для сортировки очень вероятное (для размерности Простые алгоритмы сортировки массива 8) число «пузырьков» 7 .

Последний пример дает подсказку таковой метод: чередовать перенос наверх малого (из оставшихся) элемента и перенос вниз макси­мального («топорик»?). При таком методе сортировка обоих «почти отсортированных» массивов заканчивается наименее чем за 7 шагов - это, по-видимому, просто осознать и без поясняющих рисунков. Процедура по­лучается такая:

procedure Простые алгоритмы сортировки массива Шейкер (Граница: word);

var Ввысь: boolean;

Левый,Правый: word;

begin

Ввысь:=true;

Левый:=1; Правый:=Граница;

while not Подряд(Левый,Правый) do begin

if Ввысь then begin

Сдвиг(Левый,Минимум(Левый,Правый));

inc(Левый);

end

else begin

Сдвиг(Правый,Максимум(Левый,Правый));

dec(Правый);

end;

Ввысь:=not Ввысь;

end;

end;

Функция Подряд в принципе может Простые алгоритмы сортировки массива быть применена и в других методах, потому опишем её раздельно:

function Подряд (Левый,Правый: word): boolean;

var I: word;

begin

Подряд:=false; {пока}

for I:=Левый to Правый-1 do

if Массив[I].Ключ>Массив[I+1].Ключ then exit;

Подряд:=true;

end;

К написанному нужны последующие пояснения. Опущенные подал- горитмы Минимум и Максимум Простые алгоритмы сортировки массива - функции, возвращающие номера мини­мального и наибольшего частей посреди находящихся меж их па­раметрами (подобная функция была написана нами ранее). Условие

Левый<Правый в цикле while основной процедуры можно не инспектировать поэтому, что это делается при работе функции Подряд. Пе­ременная Ввысь употребляется в качестве тумблера «пузырёк/топо­рик», а подалгоритм Простые алгоритмы сортировки массива Подряд применяется только для «внутренних» частей массива (т.е. тех, которые размещены меж 2-мя отсор­тированными частями - этого довольно). Ещё раз отметим применение подалгоритма Сдвиг (при применении заместо него подалгоритма Обмен терялся бы смысл всего способа).

Оценку эффективности способа шейкера проводить не будем по следу­ющим причинам. Во Простые алгоритмы сортировки массива-1-х, разумеется, что эффективность «в худшем» совпадает с соответственной величиной способа пузырька, а нам уже из­вестно, что даже усовершенствованная процедура ПузырекМ имеет эффективность ~ n2. Во-2-х, посчитать эффективность «в среднем» для успешных («почти отсортированных») вариантов расположения частей (где и можно было бы ждать наименьшую величину) навряд ли вообщем может Простые алгоритмы сортировки массива быть - мы приме­няли только интуитивные размышления об успешных вариантах расположения частей. В-3-х, в последующем разделе будет написана несколько более действенная «процедура‑гибрид» способов шейкера и поочередных обменов.

4.3 Способы поочередных обменов

Рассмотренный нами в прошлом подразделе метод Подряд на­водит на идея не только лишь ассоциировать порядок расположения Простые алгоритмы сортировки массива примыкающих частей массива, да и переупорядочивать их в случае неправильного рас­положения. Таким макаром, появляется последующий цикл [16]:

for I:=1 to Граница-1 do Упорядочили(I,I+1);

(этот цикл можно именовать подалгоритмом). Подалгоритм «уменьшает эн­тропию» массива, потому за некое число его применений массив станет отсортированным[17]. Но - чему равно нужное число приме­нений последнего Простые алгоритмы сортировки массива подалгоритма? Рассматривая начало его работы, мы убеждаемся что после каждого еще одного прохода по последней мере один элемент - наибольший из оставшихся - попадает на своё место, причём на последующих проходах этот элемент смещаться уже не будет.

Отсюда получаем последующие два вывода: во-1-х, для массива раз­мерности n подалгоритм довольно Простые алгоритмы сортировки массива применить n-1 раз; во-2-х, его можно поменять, всякий раз заканчивая цикл на элементе с номе­ром на 1 меньше, чем в прошлом случае. Будем именовать описанный метод способом поочередных обменов, для него выходит сле­дующая процедура сортировки:

procedure Обмены (Граница: word);

var I,K: word;

begin

for Простые алгоритмы сортировки массива K:=1 to Граница-1 do

for I:=1 to Граница-K do Упорядочили(I,I+1);

end;

Заметим, что после еще одного прохода на своём месте может ока­заться не только лишь наибольший из оставшихся частей, да и ещё несколько (на данный момент нас заинтересовывают только последующие по «старшинству»). Пример таковой ситуации нами уже подвергся Простые алгоритмы сортировки массива рассмотрению: на последнем рисунке после первого прохода на своём месте оказался не только лишь элемент (с клю­чом) 90, да и 83. Это событие дает подсказку такую модификацию метода последовательностных обменов:

procedure ОбменыМ (Граница: word);

var I,М,тахОбмен: word;

begin

maxОбмен:=Граница-1;

while max0бмен>0 do begin

M:=1;

for I:=1 to max0бмен Простые алгоритмы сортировки массива do

if Упорядочили(I,I+1) then M:=I;

maxОбмен:=М-1;

end;

end;

Тут во время каждого прохода мы запоминаем наибольший из но­меров частей, обмененных со последующими за ними, получая границу, отделяющую заранее упорядоченную часть массива (перед еще одним проходом эта граница имеет значение max0бмен+1).

Последняя Простые алгоритмы сортировки массива процедура припоминает таковой вариант сортировки, распространенный в учебниках и задачниках по информатике:

procedure ОбменыП (Граница: word);

var 1,Проход: word;

Поменяли: boolean;

begin

repeat

Поменяли:=false;

Проход:=1;

for I:=1 to Граница-Проход do begin

Поменяли:=Упорядочили(I,I+1) or Поменяли; inc(Проход);

end;

until not Поменяли;

end;

Заместо Граница-Проход может “для простоты” быть Граница Простые алгоритмы сортировки массива-1, и пере­менная Проход вообщем не употребляться. Отметим порядок логических выражений в дизъюнкции – при применении другого порядка процедура перестаёт работать, т.к. при всем этом не гарантируется просмотр всей оставшейся части масси­ва, и, как следует, постановка на место наибольшего элемента.

Невзирая на тривиальные достоинства процедуры ОбменыМ по сравне Простые алгоритмы сортировки массива­нию с Обмены и ОбменыП, понятно, что эти достоинства оказывают влияние лишь на эффективность «в среднем», нами не считаемую. Эффективность же «в худшем» у всех трёх модификаций способа поочередных обменов схожа; это идеальнее всего видно на примере «инверсного» массива:

90 83 64 51 33 32 17 11

Пробы окончить сортировку ранее времени тут фуррора не прино­сят Простые алгоритмы сортировки массива, причём и число сравнений, и число пересылок пропорциональны

(идеальнее всего последнюю формулу разъясняет вариант Обмены).

А сейчас вспомним ещё раз про способ шейкера. Оказывается, он име­ет много общего с только-только написанной нами процедурой - ведь в функ­ции Подряд мы тоже ассоциировали примыкающие элементы массива. Чтоб результаты этих Простые алгоритмы сортировки массива сравнений не пропадали, попробуем поменять элементы в случае плохого сопоставления. А чтоб было совершенно похоже на способ шейкера, будем каждый нечётный раз двигаться слева вправо (ставя при всем этом на место наибольший элемент, заодно “понижая энтропию” оставшейся части массива), а каждый чётный раз - справа влево (на место ставится Простые алгоритмы сортировки массива малый элемент). Выходит такая процедура:

procedure ШейкерМ (Граница:word);

var I,М,minОбмен,mахОбмен: word;

Ввысь: boolean;

begin

Ввысь:=false;

minОбмен:=1; mахОбмен:=Граница-1;

while minОбмен<=mахОбмен do

if Ввысь then begin

М:=Граница;

for I:=mахОбмен downto minОбмен do

if Упорядочили(I,I+1) then M:=I;

minОбмен:=М+I;

Ввысь:=false;

end

else begin M Простые алгоритмы сортировки массива:=1;

for I:=minОбмен to mахОбмен do

if Упорядочили(I,I+1) then M:=I;

тахОбмен:=М-1;

Ввысь:=true;

end;

end;

являющаяся “гибридом” способов шейкера и поочередных обменов. Разумеется, что эффективность процедуры ШейкерМ совпадает с эффектив­ностью каждого из способов поочередных обменов.


Таким макаром, можно сделать последующий вывод: эффективность каждого из обычных способов Простые алгоритмы сортировки массива сортировки массива ~ n2 .


5. Сложные методы сортировки

массива

5.1 Сортировка при помощи двоичного дерева

В отличие от разобранных выше способов сортировки, описание рассмат­риваемой в данном разделе сортировки при помощи двоичного дерева (так как российское заглавие этого способа сортировки не устоялолсь, бу­дем дальше именовать её английским сокращением – HeapSort) состоит из 2-ух частей – фактически метода и Простые алгоритмы сортировки массива его реализации[18]. Это связано с тем, что уже на данный момент может появиться таковой вопрос: какое отношение к сортировке массива имеет двоичное дерево? А если читающие данное методическое пособие уже знакомы с динамическими структурами дан­ных, создаваемыми при помощи ссылочных переменных, то вопрос может быть таким Простые алгоритмы сортировки массива: как связаны с массивами двоичные деревья (являющиеся одним из примеров динамических структур данных для представления множеств)? В данном разделе есть ответы на эти вопросы.

Поначалу разглядим метод сортировки. Будем именовать двоич­ными такие деревья, у каких любая из вершин имеет менее 2 потомков[19]. Ниже будем рассматривать только т.н. правильные Простые алгоритмы сортировки массива двоичные деревья – такие, у каких очень вероятное число уровней заполнено вполне, а у не до конца заполненного уровня все имеющие­ся верхушки (листья) размещены слева. Разумеется, что для данного n существует единственное (непомеченное) правильное двоичное дерево, содержащее ровно n вершин.

Представим для себя сортируемые элементы массива расположенными в верхушках (как листьях, так Простые алгоритмы сортировки массива и нелистьях) правильного двоичного дере­ва[20], причём так, что число, расположенное в хоть какой верхушке, не меньше, чем расположенное в хоть какой из дочерних. Будем именовать такие пра­вильные деревья верно заполненными. Существует много методов «правильно заполнить» верхушки дерева “нашими” 8 элементами [21]; два из этих методов см. на Простые алгоритмы сортировки массива приведённых рисунках.

Отметим, что для хоть какого из таких расположений любая верхушка по­мечена максимумом определяемого ею поддерева, и, а именно, корень непременно помечен наибольшим из частей массива.

Если б мы умели строить схожее двоичное дерево, то метод сортировки можно было бы записать таким макаром:

1. выстроить дерево;

2. «забрать» корень Простые алгоритмы сортировки массива – наибольший элемент, и перенести его в начало отсортированной части массива;

3. если ещё остались элементы, то перестроить дерево (так, чтоб по­лученное дерево подчинялось ранее сформулированным правилам);

4. перейти на шаг 2.

Мы написали только “заготовку” для метода сортировки HeapSort так как ещё остались невыясненными многие вопросы: «как связано двоичное дерево с массивом?»[22], «как Простые алгоритмы сортировки массива выстроить дерево?», «как его изме­нять при переносе элемента в отсортированную часть?» и др.

Ответим на главный из этих вопросов - как представить наше дво­ичное дерево в виде массива. Будем полагать, что верхушка дерева соответствует элементу массива, причём корнем является элемент с но­мером 1, а у вершины-элемента с Простые алгоритмы сортировки массива номером i потомками являются эле­менты массива с номерами 2*i и 2*i+1 (если такие есть). Нарисуем одно из рассмотренных нами правильных деревьев таким об­разом:


Вопросы всё же остаются: «как выстроить верно заполненное дере­во?», «как его изменять?».

Поначалу – построим. Будем рассматривать верхушки дерева (т.е. элементы Простые алгоритмы сортировки массива массива) с конца, перестраивая при всем этом поддерево, определяемое рассматриваемой верхушкой (корнем), если это поддерево не является верно заполненным. Отметим, что поддеревья, опре­деляемые листьями общего дерева, заранее верно заполненные (т.к. состоят из единственной вершины-корня, не имеющей потомков), потому будем перебирать с конца вершины-нелистья. Нетрудно убе­диться Простые алгоритмы сортировки массива, что независимо от чётности n - числа вершин (правильного) дерева, нелистьями являются верхушки с номерами от 1 до [n/2]. Итак, опишем подалгоритм перестройки поддерева. Предполагаем («предпо­ложение индукции»), что все собственные поддеревья рассматриваемого поддерева уже верно заполнены («базой индукции» при всем этом яв­ляются листья).

Выберем первую верхушку поддерева (корень Простые алгоритмы сортировки массива) в качестве текущей. Разглядим прямые потомки текущей верхушки (дочерние верхушки; их менее 2). Если значение текущей верхушки не меньше, чем значение наибольшей из дочерних, то процесс обработки поддерева закончен (т.к. по предположению индукции поддеревья дочерних вершин – пра­вильно заполненные). В неприятном случае поменяем местами значения текущей верхушки и наибольшей из дочерних Простые алгоритмы сортировки массива, после этого эту верши­ну (куда переместилось значение из текущей) объявим новейшей текущей. Правильность подалгоритма перестройки доказывается тем, что после описанного обмена только поддерево с корнем в новейшей текущей верхушке может не быть верно заполненным[23]. Разглядим работу подалгоритма на древнем примере. “Просеиваемое” число на рисунках обведено кружком, а Простые алгоритмы сортировки массива стрелками показаны прямые потомки верхушки, в какой оно размещено. Каждое применение подалгоритма названо проходом.


После приведённого обсуждения процедура Sift трудности не пред­ставляет:

procedure Sift (КореньПоддерева,ГраницаПоддерева: word);

var I,J,J1,J2: word;

begin

I:=КореньПоддерева;

repeat

J:=I;

{вычисляем номера дочерних вершин для J-й}

J1:=2*J; if J1>ГраницаПоддерева Простые алгоритмы сортировки массива then exit;

J2:=J1+1;

if (J2>Lim) or (Массив[J1].Ключ>Массив[J2].Ключ)

then I:=J1

else I:=J2; until not Упорядочили(I,J);

end;

Отметим, что функция Упорядочили употребляется тут не совершенно обыч­ным методом – для “оборотного” обмена, т.к. при всем этом, в отличие от Простые алгоритмы сортировки массива прошлых использований, значение первого параметра больше значе­ния второго: I>J. Пока не понятен смысл введения второго параметра (т.е. ГраницаПоддерева – ведь Sift, по-видимому, будет применена как «внутренняя» процедура метода сортировки), – но этот момент прояснится в предстоящем.

Таким макаром, для (начального) построения верно запол­ненного дерева нужно Простые алгоритмы сортировки массива выполнить последующее:

for !:=(Граница div 2) downto 1 do Sift(I,Граница);

(для примера на рисунке этот цикл делает все 4 прохода).

Итак, нами выполнена 1-ая часть метода – построение дере­ва[24]. Перенесём наибольший элемент в конец массива (на своё место), и дальше будем рассматривать дерево (массив), содержащие на 1 вер­шину (элемент) меньше Простые алгоритмы сортировки массива. В начало массива (т.е. в корень дерева) при всем этом обмене записывается число из конца массива. Это – не непременно ми­нимальный элемент массива, но, так как последний элемент массива есть лист дерева, приобретенное после таковой перестановки дерево – вероятнее всего не будет верно заполненным.

Но: где нарушается определение правильной заполненности? Исключительно Простые алгоритмы сортировки массива в корне! А с похожей ситуацией мы уже встречались - на последнем проходе при начальном построении дерева, и умеем её обрабаты­вать. (Сейчас становится понятным смысл введения второго параметра процедуры Sift – ГраницаПоддерева.) В конечном итоге мы получаем последующую про­цедуру сортировки способом HeapSort (дочерняя процедура Sift в Простые алгоритмы сортировки массива тексте опущена):

procedure HeapSort (Граница: word);

var I: word;

begin

for !:=(Граница div 2) downto 1 do Sift(I,Граница); for !:=Граница downto 2 do begin

Обмен(1,I);

Sift (1,I-1);

end;

end;

Отметим, что при наличии в массиве нескольких схожих элемен­тов приведённый метод может содержать излишние деяния, потому, может быть, 2-ой цикл лучше записать таким макаром Простые алгоритмы сортировки массива:

for I:=Граница downto 2 do

if Упорядочили(1,I) then Sift(1,I-1);

Разглядим 2-ой цикл на древнем примере (начнём с того момента, когда мы верно заполнили дерево). На рисунке показаны границы меж отсортированной и неотсортированной частями массивов (отсортированная часть- справа), а работа процедуры Sift показана «конспек­тивно» (участвующие в «просеивании» элементы Простые алгоритмы сортировки массива выделены):

Оценим эффективность способа HeapSort. Отметим, что совсем не оче­видно, что таковой непростой метод сортировки даёт отличные результаты. Но из очень обычных рассуждений следует, что эффектив­ность способа (как число сравнений, так и число обменов – в этом ал­горитме будем оценивать их сразу) пропорциональна n*logn. Вправду, число Простые алгоритмы сортировки массива операций, нужных для «просеивания элемен­та через правильное дерево, содержащее к частей, пропорционально глубине этого дерева, т.е. logк. Таким макаром, число операций и для первой, и для 2-ой частей метода пропорционально

В конечном итоге получаем эффективность способа ~n*logn, что лучше, чем у хоть какого из Простые алгоритмы сортировки массива способов, рассмотренных ранее.

5.2 «Быстрая» сортировка

Как и для предшествующего способа, будем время от времени употреблять английское сокращение наименования - QuickSort.

Аналогично дихотомии, QuickSort тоже является одним из алгорит­мов группы «разделяй и властвуй». При поиске способом дихотомии мы разделяли рассматриваемый массив (приблизительно) напополам, чтоб находить подходящий элемент исключительно в одной половине. Нельзя ли Простые алгоритмы сортировки массива тут выполнить аналогичную идею –поставить элемент с номером на место, слева от него записать наименьшие элементы, справа – огромные, после этого сортировать две половины массива независимо друг от друга? В принципе это может быть, но методы поиска элемента с номером (т.н. медианы) сложны. Но есть довольно обыкновенные Простые алгоритмы сортировки массива алгорит­мы постановки на своё место произвольно избранного элемента массива (к примеру, первого по счёту), причём таковой постановки, что в получен­ном массиве все элементы с наименьшими номерами не больше рассмат­риваемого, и напротив, все элементы с большенными номерами не меньше рассматриваемого. Один из таких алгоритмов будет описан ниже Простые алгоритмы сортировки массива.

Поставив таким макаром избранный элемент на место, будем сорти­ровать две части массива независимо друг от друга[25]. И уже на данный момент мы можем сказать, что, к огорчению, эффективность «в худшем» рассмат­риваемого способа сортировки пропорциональна п2 (как у обычных мето­дов): вправду, если массив в самом начале работы уже Простые алгоритмы сортировки массива упорядо­чен, то работа рассматриваемого метода фактически не отличается от работы метода прямого выбора. А заглавие QuickSort было дано способу за неплохую эффективность «в среднем» (подробнее см. ниже).

Итак, опишем метод таковой постановки на место избранного эле­мента, что в приобретенном массиве все элементы с наименьшими номерами не больше рассматриваемого, и Простые алгоритмы сортировки массива напротив. Выберем 1-ый элемент мас­сива; представим, что он уже находится на своём месте. Чтоб это подтвердить (либо опровергнуть), нужно, вообщем говоря, сопоставить его со всеми оставшимися элементами массива; будем перебирать их «справа налево» (т.е. от огромных номеров к наименьшим). Если при всем этом найдётся “неверный” элемент Простые алгоритмы сортировки массива (т.е. не удовлетворяющий сделанно­му предположению о том, что все элементы справа от первого больше него), то придётся поменять местами этот элемент и 1-ый. Основная мысль метода: будем полагать, что рассматриваемый нами эле­мент (прошлый 1-ый, ниже – «главный») сейчас находится на своём месте (т.е. больше Простые алгоритмы сортировки массива всех частей, стоящих слева от него). Заметим, что для проверки этого условия необходимо сопоставить его только с элементами, стоящими меж его новым и старенькым положениями в массиве. Про­должая этот процесс (т.е. после каждого обмена предполагая, что глав­ный элемент уже находится на своём месте), мы всякий раз уменьшаем число частей Простые алгоритмы сортировки массива, нужных для проверки изготовленного догадки (это число миниатюризируется по последней мере на 1), т.о. описанный метод постановки элемента на место конечен.

Продемонстрируем работу метода на примере. Главный элемент (51) везде выделен большим шрифтом и обведён в кружок. Направление сопоставления показано стрелкой. Элемент, с которым обменивается главный, также выделен большим шрифтом Простые алгоритмы сортировки массива. Как обычно, жирными линиями показаны границы меж частями массива: меж 2-мя просмотренными и одной непросмотренной.

Итак, элемент 51 находится на своём месте, причём слева от него стоят наименьшие элементы, а справа - огромные.

Сейчас нетрудно написать функцию для метода QuickSort. Ещё раз отметим, что она содержит рекурсивные (само)вызовы.

procedure Простые алгоритмы сортировки массива QuickSort (Левый,Правый: word);

label 10,20,30;

begin

if Левый>=Правый then exit;

Л:=Левый; П:=Правый;

10: while Л<П do

if Упорядочили(Л,П)

then begin inc(Л); goto 20; end

else dec(П);

goto 30;

20: while Л<П do

if Упорядочили(Л,П)

then begin dec(П); goto 10; end

else тс(Л) ;

30: QuickSort(Левый,Л-1); QuickSort(П+1, Правый Простые алгоритмы сортировки массива);

end;

Невзирая на многократное внедрение оператора goto, написан­ная нами процедура, по-видимому, удовлетворяет главным требованиям структурного программирования. Действи­тельно, в тексте очевидно выделены 3 подзадачи – движение влево, дви­жение вправо и рекурсивный вызов. Если же богатство goto покажется ненужным, то приведённый дальше другой вариант[26] дол­жен удовлетворить самых взыскательных Простые алгоритмы сортировки массива сторонников канонов струк­турного программирования:

procedure QuickSort (Левый,Правый: word);

var Л,П: word;

Вправо,У: boolean;

begin

if Левый>=Правый then exit;

Л:=Левый; П:=Правый;

Вправо:=true;

repeat

У:=Упорядочили(Л,П);

if У=Вправо then inc^) else dec(n);

if У then Вправо:=not Вправо;

until Л>=П Простые алгоритмы сортировки массива;

QuickSort (Левый,Л-1); QuickSort(П+1,Правый);

end;

Для удобства лучше написать последующую функцию Sort глобаль­ную по отношению к QuickSort:

procedure Sort (Граница: word);

begin

QuickSort(1,Граница);

end;

Выше было отмечено, что эффективность «в худшем» у способа QuickSort не лучше, чем у обычных способов сортировки, и преимущество рассмотренного способа можно Простые алгоритмы сортировки массива узреть только «в среднем». Но точно посчитать эффективность «в среднем» достаточно трудно (это тоже было увидено ранее, в разделе 2), но на помощь приходит последующее сооб­ражение. Избранный элемент массива может с равными вероятностями оказаться 1-м, 2-м, ..., n-м, потому если знать количество операций (сравнений и/либо пересылок), нужных для Простые алгоритмы сортировки массива обработки массивов раз­мерностей 1, 2,... ,п–1 (пусть для размерности i это число есть Ci), то нетрудно отыскать усреднённое число операций для массива размерности n:

Отметим, что в последней формуле учитывается и число операций (так­же – сравнений и/либо пересылок) нужных для реализации описан­ного выше подалгоритма постановки избранного элемента Простые алгоритмы сортировки массива на своё место: это – слагаемое n‑1 .

Приведённая формула отлично оценивает эффективность способа (чи­тателю полезно проверить это без помощи других). Но программка под­счёта эффективности по таковой формуле (поточнее – программка сопоставления количества операций, нужных «в среднем» для сортировки массива размерности n , с числом n*logп) не относится к рассматриваемой нами теме Простые алгоритмы сортировки массива «сортировка массива». Эта программка будет приведена в части 2 на­стоящего пособия, при описании методов преобразования рекурсивных алгоритмов в нерекурсивные. Отметим ещё, что при сопоставлении эффек­тивности «в среднем» алгоритмов HeapSort и QuickSort (к примеру, мето­дом случайного выбора исходного массива) преимущество оказывается у последнего способа: коэффициент при Простые алгоритмы сортировки массива n*logп для него оказывается меньше. (Провести такое сравнительное исследование 2-ух способов сор­тировки читателю также полезно без помощи других.)


Литература

1. Абрамов С. Лекции о трудности алгоритмов – М.: МЦНМО, 2009.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и методы.
– М.: Вильямс, 2001

3. Алексеев В. Введение в теорию трудности алгоритмов. – М.: Изд-во Простые алгоритмы сортировки массива ВМиК МГУ, 2002

4. Алексеев В., Таланов В. Графы и методы. Структуры данных. Модели вычислений. – М.: Интернет-Университет Информационных Технологий; Двучлен. Лаборатория познаний, 2006

5. Вирт Н. Методы и структуры данных. – М.: Мир, 1989.

6. Гагарина Л.Г., Колдаев В.Д. Методы и структуры данных. – М: Деньги и статистика; ИНФРА-М, 2009.

7. Головешкин В Простые алгоритмы сортировки массива, Ульянов М. Теория рекурсии для программистов – М.: ФИЗМАТЛИТ, 2006

8. Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости,теорию трудности, теорию алгоритмов, теорию связи, и тайнописью. – СПб.: БХВ, 2010.

9. Кормен Т., Лейзерсон Ч, Ривест Р. Методы: построение и анализ.- М: Вильямс, 2006

10. Кнут Д. Искусство программирования, том 1. Главные методы – М.: Вильямс, 2006.

11. Крупский В Простые алгоритмы сортировки массива. Введение в сложность вычислений. – М.: Факториал Пресс, 2006

12. Левитин А. Методы: введение в разработку и анализ методы – М.: Вильямс, 2006.

13. Липский В. Комбинаторика для программистов. – М.: Мир,1989

14. Макконнелл Дж. Базы современных алгоритмов М.: Техносфера, 2004

15. Немнюгин С. Turbo Pascal. Программирование на языке высочайшего уровня – СПб.: Питер, 2007

16. Окулов С. Программирование в Простые алгоритмы сортировки массива методах – М.:Двучлен, 2004

17. Сапоженко А. Некие вопросы трудности алгоритмов. - М.: Изд-во ВМиК МГУ, 2001

18. Харари Ф. Теория графов – М.: КомКнига, 2006

19. Шень А. Программирование: аксиомы и задачки, – М., Изд-во МЦНМО, 1995.

20. Яблонский С. Введение в дискретную арифметику, –М.: Высшая школа, 2003.


[1] Таким макаром, для серьезного определения эффективности нужно иметь определение размерности. В каждом определенном Простые алгоритмы сортировки массива случае определение размерности своё. Применительно к рассматриваемым нами задачкам сортировки и поиска, раз­мерность задачки - это просто размерность массива, т.е. Граница. Ниже это обозначе­ние будет употребляться в текстах программ и их фрагментов, а в формулах заместо Граница будем писать n .

[2]Отметим ещё раз, что мы не будем Простые алгоритмы сортировки массива использовать дополнительную память для сортировки массива.

[3] В рассматриваемых в данном пособии примерах в качестве таких операций удоб­но избрать сопоставление и пересылку частей, но время от времени имеет смысл выбирать “более сложные” операции - подалгоримы. К примеру, в большинстве алгоритмов сортиров­ки массива можно было бы подсчитывать число обменов (заместо Простые алгоритмы сортировки массива числа пересылок): ведь обмен 2-ух частей – простой метод.

[4]В задачках сортировки массивов в качестве такового огромного количества входов обычно рас­сматривается огромное количество перестановок чисел от 1 до n.

[5]Например, малая размерность, при которой среднее время работы «мед­ленного» метода ОбменыМ (раздел 4.3) более чем на 10% превосходит время Простые алгоритмы сортировки массива работы “резвого” метода QuickSort (раздел 5.2), равна 8 . А для размерно­стей, не превосходящих 5 , метод ОбменыМ работает даже резвее. Числа 5 и 8 - могут, естественно, малость изменяться зависимо от определенного метода проверки, но это беспринципно.

[6]Ещё один увлекательный (и при всем этом легкий) пример успешного внедрения ал­горитма “дели и владычествуй” (не связанный, но, с рассматриваемыми Простые алгоритмы сортировки массива тут темами) - одновременный поиск минимума и максимума в массиве. См., к примеру, [5].


proslushat-tekst-v-zapisi-i-povtorit-za-diktorom-10-glava.html
proslushat-tekst-v-zapisi-i-povtorit-za-diktorom-5-glava.html
proslushav-moj-rasskaz-i-prosmotrev-otrivok-otvette-na-voprosi-opredelite-kakie-chasti-russkoj-armii-sigrali-reshayushuyu-rol-v-poltavskom-srazhenii.html