Использовать поля связи LINKi,…,LINKn для формирования x1,…,xn во входную очередь Q

Оглавление

Введение.................................................................................................................................................................................... 5

Массивы.................................................................................................................................................................................. 5

Односвязные списки............................................................................................................................................................. 6

Оценки времени исполнения............................................................................................................................................... 6

Итак......................................................................................................................................................................................... 7

Сортировка.............................................................................................................................................................................. 7

Сортировка вставками................................................................................................................................................. 7

Теория...................................................................................................................................................................................... 7

Реализация............................................................................................................................................................................. 8

Дополнительно.................................................................................................................................................................. 9

Сортировка включениями.................................................................................................................................................. 9

Сортировка выбором....................................................................................................................................................... 10

Сортировка обменом........................................................................................................................................................ 13

Распределяющая сортировка........................................................................................................................................ 15

Сортировка Шелла......................................................................................................................................................... 16

Теория.................................................................................................................................................................................... 16

Реализация........................................................................................................................................................................... 17

Быстрая сортировка..................................................................................................................................................... 18

Теория.................................................................................................................................................................................... 18

Реализация........................................................................................................................................................................... 19

Сравнение методов....................................................................................................................................................... 22

Дополнительно................................................................................................................................................................ 23

Сортировка включениями................................................................................................................................................ 23

Сортировка выбором....................................................................................................................................................... 24

Сортировка обменом........................................................................................................................................................ 27

Словари.................................................................................................................................................................................... 29

Хеш-таблицы...................................................................................................................................................................... 29

Теория.................................................................................................................................................................................... 30

Реализация........................................................................................................................................................................... 32

Поиск в бинарных деревьях.................................................................................................................................. 34

Теория.................................................................................................................................................................................... 34

Вставка и удаление........................................................................................................................................................... 35

Реализация........................................................................................................................................................................... 36

Красно-черные деревья............................................................................................................................................. 38

Теория.................................................................................................................................................................................... 38

Вставка................................................................................................................................................................................. 39

Реализация........................................................................................................................................................................... 40

Дополнительно................................................................................................................................................................ 45

Слоёные списки............................................................................................................................................................... 45

Теория.................................................................................................................................................................................... 45

Реализация........................................................................................................................................................................... 46

Сравнение методов....................................................................................................................................................... 49

Внешняя сортировка................................................................................................................................................... 50

Теория.................................................................................................................................................................................... 51

Реализация........................................................................................................................................................................... 53

Б-деревья................................................................................................................................................................................. 53

Теория.................................................................................................................................................................................... 53

Реализация........................................................................................................................................................................... 55

Исчерпывающий поиск............................................................................................................................................ 55

Поиск с возвращением...................................................................................................................................................... 55

Метод ветвей и границ.................................................................................................................................................... 56

Задача коммивояжера...................................................................................................................................................... 56

Метод a-b-отсечений....................................................................................................................................................... 60

Динамическое прогамирование...................................................................................................................................... 66

Построение оптимальных деревьев бинарного поиска.......................................................................................... 68

Методы решета................................................................................................................................................................. 69

Литература............................................................................................................................................................................ 74

Глоссарий.............................................................................................................................................................................. 74

</DIV>Введение

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

Массивы

На рис.1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск – его алгоритм приведен на рис. 1.2. Максимальное число сравнений при таком поиске – 7; оно достигается в случае, когда нужное нам значение находится в элементе A[6].

Рис. 1.1. Массив

int function SequentialSearch (Array A, int Lb, int Ub, int Key); begin for i = Lb to Ub do if A(i) = Key then return i; return -1; end;

Рис. 1.2. Линейный поиск

Если известно, что данные отсортированы, можно применить двоичный поиск (рис. 1.3). Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам бывает нужно вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рис. 1.1, нам понадобится сдвинуть элементы A[3]:A[6] вниз - лишь после этого мы сможем записать число 18 в элемент A[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки/удаления предложены связанные списки.

int function BinarySearch (Array A, int Lb, int Ub, int Key); begin do forever M = (Lb + Ub)/2; if (Key < A[M]) then Ub = M - 1; else if (Key > A[M]) then Lb = M + 1; else return M; if (Lb > Ub) then return -1; end;

Рис. 1.3. Двоичный поиск

Односвязные списки

На рис. 1.4 те же числа, что и раньше, хранятся в виде связанного списка; слово "связанный" часто опускают. Предполагая, что X и P являются указателями, число 18 можно вставить в такой список следующим образом:

X->Next = P->Next;

P->Next = X;

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

Рис. 1.4. Односвязный список

Оценки времени исполнения

Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: «о большое от n»). Это означает, что при больших n время поиска не сильно больше, чем количество элементов. Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n²), имеют в виду, что время исполнения задачи растет не быстрее, чем некоторая константа, помноженная на квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Скорость роста O(lg n) характеризует алгоритмы типа двоичного поиска. Логарифм по основанию 2 увеличивается на 1, когда n удваивается. Вспомните - каждое новое сравнение позволяет нам искать в вдвое меньшем списке. Именно поэтому говорят, что время работы при двоичном поиске растет как lg n.

Таблица 1.1. Скорость роста нескольких функций

n	lg n	n lg n	n^1.25	n²


		2,048	1,024	65,536
4,096		49,152	32,768	16,777,216
65,536		1,048,565	1,048,476	4,294,967,296
1,048,476		20,969,520	33,554,432	1,099,301,922,576
16,775,616		402,614,784	1,073,613,825	281,421,292,179,456

Если считать, что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(lg n) потребуется 20 микросекунд, алгоритму с временем работы O(n^1.25) - порядка 33 секунд, алгоритму с временем работы O(n²) - более 12 дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O-оценки. Более точные формулировки и доказательства можно найти в приводимых литературных ссылках.

Итак...

Как мы видели, если массив отсортирован, то искать его элементы нужно с помощью двоичного поиска. Однако, не забудем, кто-то должен отсортировать наш массив! В следующем разделе мы исследуем разные способы сортировки массива. Оказывается, эта задача встречается достаточно часто и требует заметных вычислительных ресурсов, поэтому сортирующие алгоритмы исследованы вдоль и поперек, известны алгоритмы, эффективность которых достигла теоретического предела.

Связанные списки позволяют эффективно вставлять и удалять элементы, но поиск в них последователен и потому отнимает много времени. Имеются алгоритмы, позволяющие эффективно выполнять все три операции, мы обсудим из в разделе о словарях.

Сортировка

Здесь представлены несколько алгоритмов, в том числе - сортировка вставками, метод Шелла и быстрый поиск (более известный под исходным, английским, именем QuickSort). Сортировка вставками - простейший метод, который, к тому же, не требует дополнительной памяти. Метод Шелла - простая модификация сортировки вставками, которая радикально отличается от нее производительностью. По-видимому, наиболее эффективный и популярный метод - QuickSort, только он применим при сортировке больших массивов.

Сортировка вставками

Один из простейших способов отсортировать массив - сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта не на месте. Как среднее, так и худшее время для этого алгоритма - O(n²). Дальнейшую информацию можно получить в книжке Кнута [1998] [Knuth].

Теория

На рис.2.1(a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.2.1(b) для числа 1. Наконец, на рис.2.1(c) мы завершаем сортировку, поместив 2 на нужное место.

Рис. 2-1. Сортировка вставками

Если длина нашего массива равна n, нам нужно пройтись по n -1 элементам. Каждый раз нам может понадобиться сдвинуть n -1 других элементов, получая алгоритм с временем работы O(n²).

Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой - если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.

Реализация

Реализацию сортировки вставками на Си вы видите ниже. Оператор typedef T и оператор сравнения compGT следует изменить так, чтобы они соответствовали данным, хранимым в таблице.

// Коды для сортировки вставками

typedef int T; /* Тип элемента, который нужно сортировать */

typedef int tblIndex; /* Тип ключа сортировки */

#define compGT(a,b) (a > b)

void insertSort(T *a, tblIndex lb, tblIndex ub) {

T t;

tblIndex i, j;

/**********************************

* Сортировка массива a[lb..ub] *

**********************************/

for (i = lb + 1; i <= ub; i++) {

t = a[i];

/* Элементы сдвигаются вниз до */

/* найденного места вставки. */

for (j = i-1; j >= lb && compGT(a[j], t); j--)

a[j+1] = a[j];

/* Вставка */

a[j+1] = t;

}

Дополнительно

Здесь рассмотрим более подробно группу простых методов сортировки. Кроме того в этом разделе мы будем рассматривать программы сортировок в нотации языка Pascal. Поэтому некоторые методы основного раздела могут здесь быть рассмотрены повторно. Итак…

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива A в массив B, пока не представляют для нас интереса. Таким образом, выбирая метод сортировки, классификацию алгоритмов удобно проводить в соответствии с их эффективностью, т.е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С необходимых сравнений ключей и М пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов.

Хотя хорошие алгоритмы сортировки требуют порядка (n*log(n))сравнений, мы сначала обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка n^2 сравнений ключей. Изучение простых методов важно по следующим причинам:

1. Простые методы очень хорошо подходят для разъяснения свойств большинства принципов сортировки.

2. Программы, основанные на этих методах, легки для понимания и коротки. Следует помнить, что программы тоже занимают память.

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

Методы, сортирующие in situ, можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1. Сортировка включениями.

2. Сортировка выбором.

3. Сортировка обменом.

Теперь рассмотрим и сравним эти три принципа. Программы работают с массивом A, компоненты которой нужно рассортировать in situ,в этих программах используются типы данных item и index, определенные так:

type index = 0 .. n;

var A: array [1 .. n] of item;

Сортировка включениями

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

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

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность A[1],...,A[i-1] и входную последовательность A[i],...,A[n]. На каждом шаге, начиная с i=2 и увеличения i на единицу, берут первый элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Пример сортировки “просеивание”.

начальные ключи 44 55 12 42 94 18 06 67

i=2 44 55 12 42 94 18 06 67

i=3 12 44 55 42 94 18 06 67

i=4 12 42 44 55 94 18 06 67

i=5 12 42 44 55 94 18 06 67

i=6 12 18 42 44 55 94 06 67

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 67 94

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

for i:= 2 to n do

begin x:= A[i]

"вставить х на подходящем месте в A[1]...A[i]"

end

При поиске подходящего места чередовать сравнения и пересылки, т.е. как бы "просеивать" х, сравнивая его с очередным элементом A[j] и либо вставляя х, либо пересылая A[j] направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях:

Найти элемент A[j] с ключом меньшим, чем ключ х.

Достигнут левый конец готовой последовательности.

Этот типичный пример цикла с двумя условиями окончания дает нам возможность рассмотреть хорошо известный прием фиктивного элемента ("барьера"). Его можно легко применить в этом случае, установив барьер A[0] = х. (Заметим, что для этого нужно расширить диапазон индексов в описании A до 0,...,n). Окончательный алгоритм представлен ниже в виде программы.

Реализация

procedure StraightInsertion;

var i,j: index; x: item;

begin

for i:= 2 to n do

begin x:= A[i]; A[0]:= x; j:= i-1

while (x.key < A[j].key) do

begin A[j+1]:=A[j]; j:=j-1;

end;

A[j+1]:=x;

end;

Сортировка бинарными включениями

Алгоритм сортировки простыми включениями легко улучшить, если обратить внимание на то, что готовая последовательность A[1],...,A[i],в которую требуется включить новый элемент, уже упорядочена. Место включения можно найти значительно быстрее, если применить бинарный поиск. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями, он приведен ниже в программе.

Реализация

procedure BinaryInsertion;

var i,j,l,r,m: index; x: item;

begin

for i:= 2 to n do

begin x:=A[i]; l:=1; r:=i-1;

while (l<=r) do

begin m:=(l+r) div 2;

if (x.key<A[m].key) then r:=m-1 else l:=m+1;

end;

for j:=i-1 downto l do A[j+1]:=a[j];

A[l]:=x;

end;

Сортировка выбором

Линейный выбор

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

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

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

Линейный выбор с обменом

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

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

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

Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не останется только один элемент - наибольший. Этот метод продемонстрирован на тех же восьми ключах:

Начальные ключи 44 55 12 42 94 18 06 67

i=2 06 55 12 42 94 18 44 67

i=3 06 12 55 42 94 18 44 67

i=4 06 12 18 42 94 55 44 67 (42 уже на месте)

i=5 06 12 18 42 94 55 44 67

i=6 06 12 18 42 44 55 94 67 (55 уже на месте)

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 67 94

Программу можно представить следующим образом:

for i:= 1 to n-1 do

begin "присвоить k индекс наименьшего элемента из A[i] ...A[n]”

"поменять местами A[i] и A[k]"

end

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

Реализация

procedure StraightSelection;

var i,j,k: index; x: item;

begin for i:= 1 to n-1 do

begin k:= i; x:= A[i];

for j:= i+1 to n do

if (A[j].key < x.key) then

begin k:= j; x:= A[j];

end;

A[k]:= A[i]; A[i]:= x;

end;

Линейный выбор с подсчетом

Метод сортировки с подсчетом описывается в литературе как процедура упорядочения внутреннего списка чисел. Фактически, это не метод сортировки, а технический приём, который можно использовать в различных методах для сокращения количества обменов или их полного устранения. Он является формой индексирования, в которой счетчик относительной позиции каждого элемента корректируется в течение процесса сравнения. Здесь он описан применительно к линейному выбору.

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

Реализация

procedure ViborSPodschetom;

var

i,j:index;

count: array [index] of integer;

B: array [index] of item;

begin

for i:=1 to n do count[i]:=0;

for i:=1 to n-1 do

begin

for j:=i+1 to n do

begin

if (A[i].key<A[j].key) then count[j]:=count[j]+1 else count[i]:=count[i]+1;

end;

for i:=1 to n do B[count[i]+1]:=A[i];

for i:=1 to n do A[i]:=B[i];

end;

Сортировка обменом

Парный обмен

Метод парного обмена(также называемый “нечётно-чётная перестановка”) состоит из различного числа “нечётных” и “чётных” просмотров. При нечётных просмотрах каждый элемент из нечетной позиции сравнивается со своим соседом из чётной позиции и больший из них занимает четную позицию. Нисходящий просмотр списка продолжается до тех пор, пока последний нечетный (N-1) не сравнивается с последним четным элементом (N). Если нечетное число элементов, то последний элемент не будет участвовать в сравнении. В течение каждого просмотра ведется подсчет обменов.

При четных просмотрах четные позиции сравниваются с соседними нечетными. Обмены выполняются тогда, когда надо, чтобы больший из пары занял нечетную позицию. Таким образом, ключи с большими значениями перемещаются на дно списка. При этом должно быть столько просмотров, сколько необходимо для того, чтобы переместить в позицию число, наиболее удаленное от своей конечной позиции. Затем выполняется заключительный просмотр, необходимый для того, чтобы опознать упорядоченность. В течение этого просмотра счетчик обменов равен 0. Данный метод требует по крайней мере двух просмотров – одного нечётного и одного чётного.

Парный обмен, просмотры

Начальные ключи. i=2 3 4 5 6 7 8

44 06 06 06 06 06 06 06

55 44 12 12 12 12 12 12

12 55 44 18 18 18 18 18

42 12 55 44 42 42 42 42

94 42 18 55 44 44 44 44

18 94 42 42 55 55 55 55

06 18 94 67 67 67 67 67

67 67 67 94 94 94 94 94

Реализация

procedure ParnajaSort;

var

i:index;

x:item;

nechet:boolean;

obmen,j:integer;

begin

nechet:=true; j:=0;

repeat

obmen:=0;

if nechet then i:=1 else i:=2;

repeat

if (A[i].key > A[i+1].key) then

begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;

obmen:=obmen+1;

end;

i:=i+2;

until (i>=n);

j:=j+1;

if nechet=true then nechet:=false else nechet:=true;

until(obmen=0) and (j>=2);

end;

Стандартный обмен

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

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

Начальные ключи. i=2 3 4 5 6 7 8

44 06 06 06 06 06 06 06

55 44 12 12 12 12 12 12

12 55 44 18 18 18 18 18

42 12 55 44 42 42 42 42

94 42 18 55 44 44 44 44

18 94 42 42 55 55 55 55

06 18 94 67 67 67 67 67

67 67 67 94 94 94 94 94

Этот метод широко известен как сортировка методом пузырька. Его простейший вариант приведен в программе ниже.

procedure BubbleSort;

var i,j: index; x: item;

begin for i:= 2 to n do

begin for j:= n downto i do

if (A[j-1].key > A[j].key) then

begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;

end;

end; {BubbleSort}

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

Этот предыдущий алгоритм легко оптимизировать. Пример показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм – это запомнить, производится ли на данном проходе какой - либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запомнить не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами меньшими этого индекса k, уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе вместо того чтобы двигаться до установленной заранее нижней границы i. Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в тяжелом конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент легкого конца будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив 12,18,42,44,55,67,94 06 будет рассортирован при помощи метода пузырька за один проход, а сортировка массива 94,06,12,18,42,44,55,67 потребует семи проходов. Эта неестественная асимметрия подсказывает нам третье улучшение: менять направление следующих один за другим проходов. Мы назовем полученный в результате алгоритм шейкер-сортировкой. Его работа показана ниже на тех же восьми ключах, использованных в предыдущей таблице.

Программа шейкер-сортировки приведена ниже.

Реализация

procedure ShakeSort;

var j,k,l,r: index; x: item;

begin l:=2; r:=n; k:=n;

repeat

for j:=r downto l do

if (A[j-1].key > A[j].key) then

begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;

k:=j;

end;

l:=k+1;

for j:=l to r do

if (A[j-1].key > A[j].key) then

begin x:=A[j-1]; A[j-1]:=A[j]; A[j]:=x;

k:=j;

end;

r:=k-1;

until (l>r);

end; {ShakeSort}

i = 2 3 3 4 4

r = 8 8 7 7 4

^ v ^ v ^

44 06 06 06 06

55 44 44 12 12

12 55 12 44 18

42 12 42 18 42

94 42 55 42 44

18 94 18 55 55

06 18 67 67 67

67 67 94 94 94

Распределяющая сортировка

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

Мы полагаем, что каждое из имен x₁, x₂, …, x_n имеет вид

x_i=( x_i,p,x_i,p-1,…,x_i,1)

и их нужно отсортировать в возрастающем лексикографическом порядке, т.е.

x_i=(x_i,p,x_i,p-1,…,x_i,1)<(x_j,p,x_j,p-1,…,x_j,1)=x_j

тогда и только тогда, когда для некоторого tp имеем x_i,l= x_j,l для l>t и x_i,t<x_j,t. Для простоты будем считать, что 0x_i,l<r, и поэтому имена можно рассматривать как целые, представленные по основанию r, так что каждое имя имеет p r-ичных цифр. Чтобы не было имен разной длины, более короткие имена дополняются нулями.

Цифровая распределяющая сортировка основана на наблюдении, что если имена уже отсортированы по младшим разрядам l, l-1, …, 1, то их можно полностью отсортировать, сортируя только по старшим разрядам p, p-1,…, l+1 при условии, что сортировка осуществляется таким образом, чтобы не нарушить относительный порядок имен с одинаковыми цифрами в старших разрядах. Эта идея лежит в основе механических сортировальных машин для перфокарт; для сортировки карт в полях, скажем, от 76-й до 80-й колонки, они сортируются в возрастающем порядке по 80-й колонке, потом по 79-й колонке и т.д. включая и 76-ю колонку. Каждая сортировка по колонке состоит из чтения колонки каждой карты и физического перемещения карты наверх стопки, которая отвечает цифре, пробитой в этой колонке карты. Как только все карты помещены в соответствующие стопки, стопки объединяются вместе в порядке возрастания; затем процесс повторяется для следующей колонки слева. Эта процедура проиллюстрирована на примере трехзначных чисел.

Заметим, что как к стопкам, так и к самой таблице обращаются по правилу “первым включается – первым исключается”, и поэтому лучшим способом их представления являются очереди. В частности, предположим, что с каждым ключом x_i ассоциируется поле связи LINK_i; тогда эти поля связи можно использовать для сцепления всех имен в таблице вместе во входную очередь Q. При помощи полей связи можно также сцеплять имена в очереди Q₀,Q₁,…,Q_r-1, используемые для представления стопок. После того как имена распределены по стопкам, очереди, представляющие эти стопки, связываются вместе для получения вновь таблицы Q. В результате применения алгоритма очередь Q будет содержать имена в порядке возрастания; т.е. имена будут связаны в порядке возрастания полями связи, начиная с головы очереди Q.

Алгоритм распределяющей сортировки

Использовать поля связи LINKi,…,LINKn для формирования x1,…,xn во входную очередь Q

вначале сделать очереди Q₀,…,Q_r-1 пустыми

while Q не пуста do пусть X=(x_p,x_p-1,…,x₁)

For j=1 to p do Q_xjX