ОБМЕННАЯ СОРТИРОВКА

Простой обмен. Алгоритм основан на сравнении и перемене мест соседних элементов, если их ключи не упорядочены. Процесс продолжается до тех пор, пока не будут упорядочены все элементы исходной последовательности.

На рис. 5.5 приведен пример сортировки последовательности значений 44, 55, 12, 42, 94, 06, 18, 67 методом простого обмена. Сортируемые элементы расположены вертикально. Проходы массива (сравнения ключей и перестановка соседних элементов) осуществляются с его конца (снизу).

Рис. 5.5. Сортировка простым обменом

На каждом проходе наименьший элемент оставшейся последовательности продвигается к началу массива и исключается из последующих сравнений. В примере каждый такой элемент подчеркнут. Результат / -го прохода показан в (/ + 1)-м столбце таблицы. Если значение ключа элемента уподобить его весу, то можно сказать, что элемент «всплывает» до уровня, соответствующего его весу. Поэтому метод простого обмена называют также «пузырьковой сортировкой». Реализуется он просто:

for i:=2 to n do begin for j:=n downto i do begin

if a[j-1].key>a[j].key then begin

ltem:=a[j-1]; aQ-1]:=aQ]; a[j]:=ltem; end; //if end; //for/' end; //fori

В среднем число проходов массива равно п-1 , на каждом проходе сравнивается n-i пар элементов, где / — номер прохода (/= 1,2,..., п - 1).

Характеристики метода: С ~ 0,5п²; Р ~ 0,25п².

Улучшения алгоритма простого обмена. Из приведенного выше примера видно, что последние три прохода не влияют на порядок элементов из-за того, что они уже отсортированы. Отсюда очевидны улучшения алгоритма простого обмена:

• 1) запоминание наличия обменов в процессе очередного прохода; если в последнем проходе перестановок не было, то сортировку можно завершать;
• 2) запоминание не только фактов обмена, но и места (индекса) последнего обмена. Все пары соседних элементов, расположенных выше этого места, уже находятся в нужном порядке, поэтому индекс последнего обмена может служить границей просмотра еще неотсортированной последовательности.

Шейкер-сортировка. Обратимся еще раз к приведенному выше примеру сортировки методом простого обмена. Можно заметить, что «легкий» элемент за один проход «всплывает» на соответствующий его весу уровень, зато «тяжелый» элемент «опускается» только на одну позицию. Если массив просматривать сверху вниз, то скорости передвижения «тяжелых» и «легких» элементов поменяются местами. Из этого факта следует еще одно возможное улучшение обменной сортировки: чередование направлений следующих друг за другом просмотров, что приводит к уменьшению требуемого числа просмотров.

Проиллюстрируем алгоритм тем же числовым примером, расположив исходную последовательность по-прежнему вертикально (см. рис. 5.6).

Left= 2 3 3 4 4

Right= 8_8_7_7_4

Рис. 5.6. Шейкер-сортировка

Результат каждого прохода показан в соответствующем столбце справа, направления просмотров указаны стрелками. Для каждого просмотра устанавливаются левая Left и правая Right границы. Их начальные значения: Left = 2, Right = 8. На просмотре снизу вверх сравниваются и обмениваются местами элементы aj__{ и я, для j = Right, Right - 1,..., Left. После просмотра устанавливается новое значение левой границы Left = к +1, где к — индекс последнего обмена.

На следующем просмотре — сверху вниз — сравниваются и обмениваются местами элементы а ,_ч и для j = Left, Left +1,..., Right, после чего устанавливается новое значение правой границы Right -к-1, где к — индекс последнего обмена. Чередование просмотров осуществляется до тех пор, пока левая и правая границы не встретятся.

В программе Шейкер-сортировки Last — место последнего обмена:

Left:=2;

Right:=n;

Last:=n;

repeat

for j:=Right downto Left do begin //просмотр снизу вверх if a[j-1].key>a[j].key then begin //обмен ltem:=a[j-1];

a[j-1]:=aQ];

a[j]:=ltem;

Last:=j;

//запоминание места последнего обмена

end; end;

Left:=Last+1; // начиная с места последнего обмена

for j:=Left to Right do begin //просмотр сверху вниз

if ар-1].key>a[j].key

then begin //обмен ltem:=a[j-1];

a[j-1]:=a[j];

a[j]:=ltem;

Last:=j; //запоминание места последнего обмена

end;

end;

Right:=Last-1; until Left>Right;

Анализ улучшенных алгоритмов обменной сортировки показывает, что введенные улучшения не дают существенного выигрыша по сравнению с алгоритмом простого обмена: С < 0,5я²; Р ~ 0,25п². Число перемещений не изменяется, число сравнений немного сокращается, но по-прежнему остается пропорциональным п².

Шейкер-сортировку целесообразно использовать в случаях, когда известно, что исходная последовательность почти упорядочена.

Метод четных и нечетных транспозиций. Сортировка выполняется следующим образом. На очередном шаге сравниваются и, если необходимо, обмениваются местами a_j и a_j + 1 для всех нечетных /. На следующем шаге эти действия выполняются для всех четных /. Эти два шага повторяются до тех пор, пока массив не будет отсортирован.

Обменная сортировка с разделением (быстрая сортировка). Разработана Хоаром в 1962 г. Результаты оказались настолько хорошими, что на настоящее время это наиболее быстрая сортировка.

Метод заключается в следующем. Случайным образом выбирается какой-либо элемент* массива, массив просматривается слева направо, пока не будет найден я,- >* , затем массив просматривается справа налево, пока не будет найден о <х . Эти элементы меняются местами, и процесс просмотра с обменом продолжается, пока два просмотра не встретятся где-то в середине массива.

В результате массив разделится на две части: левую (с ключами, меньшими ключа*) и правую (с ключами, большими ключа*). Сортировка заключается в проведении процедуры разделения сначала для всего массива, затем каждой части, затем частей каждой части и т.д., пока каждая часть не будет содержать один элемент.

Процедура сортировки может быть реализована рекурсивно. В программе Quicksort: Left, Right — левая и правая границы просмотра, TIndex, Titern — типы индекса и элемента массива.

procedure QuickSort(Left, Right: Tlndex);

var

i, j: Tlndex; x, w : Tltem;

begin

i:=Left; j:=Right; x:=a[(Left+Right) div 2];

repeat

while a[i].keyx.key do Dec(j); if i<=j

then begin

w:=a[i]; a[i]:=a[j]; a[j]:=w; lnc(i); DecG);

end; until i>j;

if Lefti then QuickSort(i, Right);

end;

В процессе одного разделения проводится п сравнений и примерно обменов (зависит от выбора л;). Наилучшие результаты

будут получены, если в качестве л: будет выбрана медиана последовательности (элемент, значение которого больше либо равно значений половины элементов и меньше либо равно значений другой половины элементов). В этом случае каждое разделение разбивает массив на две равные части, и число проходов сортировки равно

log₂ п , С ~ «log₂ п , Р ~ ^П °^^2П . Если граница выбирается случайным образом, то эффективность несколько ухудшается. Метод неустойчив.

К недостаткам алгоритма быстрой сортировки можно отнести то, что он не эффективен при малых п (как и все усовершенствованные методы), и в наихудшем случае (неудачный выбор л;, например, наибольшее значение в массиве и подмассивах) сортировка становится медленной: С ~ п².

СОРТИРОВКА ВЫБОРОМ

Сортировка с помощью простого выбора. Метод основан на следующем. Сначала методом последовательного поиска отыскивается элемент с наименьшим ключом, затем он меняется местами с первым элементом и исключается из дальнейшего рассмотрения. Из оставшихся п-1 (от 2-го до я-го) элементов вновь находится наименьший, меняется местами со вторым элементом и также исключается из исходной последовательности. Этот процесс повторяется с оставшимися п- 2, п - 3 , ... элементами до тех пор, пока не останется один элемент.

В программе сортировки выбором к — адрес минимального элемента:

for i:=1 to n-1 do begin

k:=i;

ltem:=a[i];

for j:=i+1 to n do begin

if a[j].key

then begin

k:=j;

ltem:=a[j]; end; //if end; //forj a[k]:=a[i]; a[i]:=ltem; end; //fori

Число сравнений не зависит от начального порядка ключей и равно С ~ 0,5гг , число перестановок Р ~пп(п), откуда следует, что алгоритм с простым выбором предпочтительнее простого обмена и простых вставок.

Выбор из дерева или метод турнира с выбыванием. Для улучшения сортировки выбором желательно от каждого прохода получать больше информации, нежели просто указание на наименьший элемент.

Например, с помощью сравнений можно определить наимень-

п

шии ключ из каждой пары, при помощи следующих — сравнении — выбрать наименьший из каждой пары наименьших и т. д. Таким образом, на первом шаге с помощью п-1 сравнений можно построить дерево выбора, и определить корень как наименьший ключ.

Рассмотрим пример сортировки последовательности 44, 55, 12, 42, 94, 06, 18, 67. В результате выполнения первого шага будет построено дерево выбора, приведенное на рис. 5.7.

I-06-1

I-12-1 i-06-1

I— 44 —i |~ 12 —i |— 18 —i |— 06 —|

44 55 12 42 94 18 06 67

Рис. 5.7. Исходное дерево выбора для сортировки последовательности 44, 55, 12, 42, 94, 06, 18, 67

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

В результате выполнения второго шага будет построено дерево выбора, приведенное на рис. 5.8.

I- -1

I-12-1 |-18-1

I— 44 —| I^- 12 —I |— 18 —I |— 67 —|

44 55 12 42 94 18 оо 67

Рис. 5.8. Исключение наименьшего значения 06 в дереве выбора

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

На каждый шаг требуется о%₂ п сравнений, т.е. С = поё₂ п , Дополнительно нужно п шагов на построение дерева. Ускорение достигнуто за счет усложнения структуры хранения информации — дерево требует 2п- единиц памяти при его реализации на базе массива. Дыры (оо) постепенно заполняют все дерево и приводят к большому числу ненужных сравнений.

Экономии памяти можно добиться, если в узлах дерева хранить не сами элементы с ключами, а указатели этих ключей. Тогда объем необходимой памяти составит п исходных элементов и п -1 указателей.

Пирамидальная сортировка. Разработана Дж. Уильямсом и позволяет хранить дерево из п элементов исходной последовательности в п единицах памяти в виде пирамиды, которая определяется как последовательность ключей А,, А_/+1,..., к_г такая, что А, < А_2/, А, < А_2/+1 для • / ^г

каждого 1 = 1,..., — .

Пример массива А из 15 элементов, расположенный в виде дерева, приведен на рис. 5.9.

I-^}п-1 I-Аз-1

|—A4—I [—А 5—1 [—Аб—I |—А7—|

As А9 А10 А11 А12 А13 А14 А15

Рис. 5.9. Массив из 15 элементов, расположенный в виде пирамиды

Элемент А, является ее наименьшим элементом:

А, = тт(/?1,АД.

Предположим, что дана пирамида с элементами /г_/+1и нужно добавить новый элемент х для того, чтобы сформировать расширенную пирамиду А,, А_/+1,..., А_г.

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

Исходная |-Ai-1 Результат |-06-1

пирамида ₍—42—, —06—| просеивания |—42—, ,—12—|

55 94 18 12 ключа 44 55 94 18 44

Рис. 5.10. Расширение пирамиды «просеиванием» элемента 44

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

Процедура просеивания (Left, Right — границы исходной пирамиды):

procedure Sift(Left, Right: Tlndex);

var

i, j: Tlndex: x: Tltem; begin i:=Left; j:=2*Left; x:=a[Left];

while j<=Right do begin // выбор наименьшего из смежных с х: if j

then

if a[j].key>a[j⁺1].key then lnc(j); if x.key<=a[j].key then Break; a[i]:=a[j]; i:=j; j:=2*i; end; a[i]:=x;

end; //procedure Sift

Для построения пирамиды P. Флойд предложил следующий способ. Дан массив h_x,...,h_n, в котором элементы h_n ,...,h_n уже обра-

—+1 2

зуют пирамиду, так как нет индексов j = 2/ (или j = 2/ +1). Эти элементы составляют листья двоичного дерева. Далее необходимо расширить пирамиду влево: добавить на каждом шаге один элемент и с помощью просеивания поместить его на соответствующее место:

Left:=(n div 2) +1;

while Left>1 do begin Dec(left);

Sift(Left, n);

end;

На рис. 5.11 проиллюстрирован процесс построения пирамиды для последовательности 44, 55, 12, 42, 94, 06, 18, 67 (вертикальная черта — граница пирамиды).

Рис. 5.11. Иллюстрация процесса построения пирамиды

На рис. 5.12 показана построенная пирамида. Для каждого элемента выполняются условия: /?, < h_2j, h) < h_2j+].

I-Об-!

I-42-, | 12 |

I—55 94 18 44

Рис. 5.12. Результат построения пирамиды

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

Процесс сортировки описывается следующим образом:

Right:=n;

while Right>1 do begin x:=a[1l; a[1]:=a[Rightl; a[Rightl:=x;

Dec(Right); Sift(1, Right);

end;

На рис. 5.13 проиллюстрирован процесс сортировки (вертикальная черта — граница пирамиды).

Рис. 5.13. Иллюстрация процесса сортировки с помощью пирамиды

Сортировка выполняется по убыванию, для достижения противоположного порядка необходимо изменить упорядочивающие отношения в процедуре Sift (строки 13 и 14):

if a0].key=a[j].key then Break;

С

. Алгоритм неустойчивый и имеет несколько неестествен

Эффективность пирамидальной сортировки тем больше, чем больше п. Число сравнений С~ nog₂n , число перемещений пlog?п

ное поведение.

СОРТИРОВКА СЛИЯНИЕМ

Слияние означает объединение двух или более отсортированных последовательностей в единую упорядоченную последовательность путем поочередного сравнения элементов исходных последовательностей и выдачи младшего из них в результирующую.

Сортировка простым слиянием:

• 1) последовательность а разбивается на две половины: Ь и с;
• 2) части Ъ и с сливаются, при этом одиночные элементы образуют упорядоченные пары;
• 3) полученная последовательность под именем а вновь обрабатывается, как указано в пунктах 1 и 2, при этом упорядоченные пары образуют четверки;
• 4) повторяя предыдущие шаги, сливаем четверки в восьмерки и т.д., каждый раз «удваивая» длину слитых последовательностей пока не будет упорядочена вся последовательность.

Если одна из частей Ь или с будет исчерпана, то оставшаяся часть другой копируется (переписывается) в выходную последовательность.

Возьмем в качестве примера последовательность: 44 55 12 42 94 18 06 67

После разбиения (шаг 1) получаем две последовательности 44 55 12 42 и 94 18 06 67

Слияние одиночных компонент (т.е. упорядоченных последовательностей длины 1) в упорядоченные пары дает 44 941 18 55 06 12 I 42 67

Делим массив пополам и сливаем упорядоченные пары:

06 12 44 94 18 42 55 67

Третье разделение и слияние приводят к желаемому результату: 06 12 18 42 44 55 67 94

Разбиение последовательности а на части Ьи с можно осуществлять, сливая на первом проходе соседние элементы, на следующем — соседние пары, затем четверки и т.д. Можно при слиянии брать элементы с двух концов массива и слитые пары поочередно записывать на разные концы нового массива. При этом сразу будет получаться разделенная последовательность с упорядоченными парами элементов.

Сортировка методом простого слияния требует Р~по%₂п пересылок элементов и несколько меньшего числа сравнений, поскольку при копировании остатков сравнения ключей не выполняются. При реализации алгоритма требуется п элементов резервной памяти.

Контрольные вопросы и задания

• 1. Выполните упорядочивание последовательности 1,7, 3, 2, 0, 5, 0, 8 с помощью методов «пузырька», сортировки вставками, сортировки посредством выбора.
• 2. Выполните упорядочивание последовательности 22, 36, 6, 79, 26, 45, 75, 13, 31, 62, 27, 76, 33, 16 используя быструю сортировку, сортировку вставками, пирамидальную сортировку.
• 3. Предположим, что необходимо сортировать список элементов, состоящий из уже упорядоченного списка, который следует за несколькими «случайными» элементами. Какой из рассмотренных методов сортировки наиболее подходит для решения такой задачи?
• 4. Какой из рассмотренных методов сортировки устойчив?
• 5. Какие методы сортировки обладают естественным поведением?
• 6. Предположим, что в алгоритме быстрой сортировки в качестве опорного элемента выбирается первый элемент сортируемого подмножества. Какие изменения следует сделать в алгоритме быстрой сортировки, чтобы избежать «зацикливания» в случае последовательности равных элементов?
• 7. Рассмотрим алгоритм случайной сортировки, примененный к массиву А[..п целых чисел: выбирается случайное число / из интервала от 1 до п и меняются местами элементы А[ 1] и А[(, процесс повторяется до тех пор, пока не будут упорядочены все элементы массива. Каково ожидаемое время выполнения этой сортировки?
• 8. Напишите программу нахождения моды (наиболее часто встречаемого элемента) в последовательности из п элементов.
• 9. Напишите программу нахождения к наименьших элементов в массиве длиной п. Для каких значений к эффективнее сначала выполнить сортировку всего массива, а затем взять к наименьших элементов, вместо поиска наименьших элементов в неупорядоченном массиве?
• 10. Напишите программу нахождения наибольшего и наименьшего элементов в массиве. Может ли эта программа обойтись менее чем 2«-3 сравнениями?
• 11. Напишите программу вычисления медианы последовательности из п элементов (элемент, значение которого больше либо равно значений половины элементов и меньше либо равно значений другой половины элементов).

Лабораторная работа 5. ВНУТРЕННЯЯ СОРТИРОВКА

Задание

Составить программу сортировки заданной последовательности. Программу необходимо выполнить с двумя вариантами исходных данных:

• • отладочный (10 элементов), демонстрирующий результаты всех проходов алгоритма сортировки;
• • рабочий (50 элементов), в результате обработки которого выводятся отсортированная последовательность, а также значения параметров эффективности: число сравнений ключей С и число перестановок элементов Р(или число переключений связей Кдля списка).

Исходные данные и результаты работы программы (демонстрационные и рабочие) разместить в текстовых файлах.

В вариантах с нечетными номерами сортируются записи, состоящие из двух полей: строки и числового ключа.

В вариантах с четными номерами сортируется по алфавиту последовательность строковых переменных.

В вариантах, отмеченных звездочкой, исходная последовательность организована в виде связанной структуры — списка. В остальных вариантах сортируемая последовательность — массив. Варианты заданий приведены в табл. 5.1.

Варианты заданий к лабораторной работе 5

Рекомендации по выполнению работы

Для создания таблицы рекомендуется создать текстовый файл, содержащий порядка 100 элементов.

Сначала выполнить работу в отладочном (демонстрационном) режиме, для чего прочитать из этого файла первые 10 элементов, создать таблицу и отсортировать ее, демонстрируя все шаги алгоритма (индексы и результаты сравнений).

Затем выполнить работу в рабочем режиме. Для этого открыть тот же файл с исходными данными для чтения, прочитать из него все элементы, создать таблицу и отсортировать ее, подсчитывая количество операций сравнения ключей и перестановок на каждом шаге сортировки. В файл результатов вывести отсортированную таблицу и результаты исследования процедуры сортировки (число сравнений ключей и перестановок, потребовавшихся для сортировки). Результаты сравнить с теоретическими характеристиками сложности исследуемого метода.