2014-02-24
1566
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N2). Количество пересылок - N.
Алгоритм сортировки простой выборкой иллюстрируется программным примером 3.7.
В программной реализации алгоритма возникает проблема значения ключа "пусто". Довольно часто программисты используют в качестве такового некоторое заведомо отсутствующее во входной последовательности значение ключа, например, максимальное из теоретически возможных значений. Другой, более строгий подход - создание отдельного вектора, каждый элемент которого имеет логический тип и отражает состояние соответствующего элемента входного множества ("истина" - "непусто", "ложь" - "пусто"). Именно такой подход реализован в нашем программном примере. Роль входной последовательности здесь выполняет параметр a, роль выходной - параметр b, роль вектора состояний - массив c. Алгоритм несколько усложняется за счет того, что для установки начального значения при поиске минимума приходится отбрасывать уже "пустые" элементы.
|
|
|
{===== Программный пример 3.7 =====}
Procedure Sort(a: SEQ; var b: SEQ);
Var i, j, m: integer;
c: array[1..N] of boolean; {состояние эл-тов вх.множества}
begin
for i:=1 to N do c[i]:=true; { сброс отметок }
for i:=1 to N do {поиск 1-го невыбранного эл. во вх.множестве}
begin j:=1;
while not c[j] do j:=j+1;
m:=j; { поиск минимального элемента }
for j:=2 to N do
if c[j] and (a[j]<a[m]) then m:=j;
b[i]:=a[m]; { запись в выходное множество }
c[m]:=false; { во входное множество - "пусто"}
end; end;
ОБМЕННАЯ СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется его, так называемый, обменный вариант. При обменной сортировке выборкой входное и выходное множество располагаются в одной и той же области памяти; выходное - в начале области, входное - в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество - пустое. По мере выполнения сортировки входное множество сужается, а выходное - расширяется.
Обменная сортировка простой выборкой показана в программном примере 3.8. Процедура имеет только один параметр - сортируемый массив.
{===== Программный пример 3.8 =====}
Procedure Sort(var a: SEQ);
Var x, i, j, m: integer;
begin
for i:=1 to N-1 do { перебор элементов выходного множества}
{ входное множество - [i:N]; выходное - [1:i-1] }
begin m:=i;
for j:=i+1 to N do { поиск минимума во входном множестве }
if (a[j]<a[m]) then m:=j;
{ обмен 1-го элемента вх. множества с минимальным }
if i<>m then begin
x:=a[i]; a[i]:=a[m]; a[m]:=x;
end;end; end;
Результаты трассировки программного примера 3.8 представлены в таблице 3.5. Двоеточием показана граница между входным и выходным множествами.
|
|
|
Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но порядок алгоритма остается степенным - O(N2). Количество перестановок N-1, но перестановка, по-видимому, вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.
Таблица 3.5
| Шаг | Содержимое массива а |
| исходный результат | : 242 447 286 708 24 11 192 860 937 561 11:447 286 708 24 242 192 860 937 561 11 24:286 708 447 242 192 860 937 561 11 24 192:708 447 242 286 860 937 561 11 24 192 242:447 708 286 860 937 561 11 24 192 242 286:708 447 860 937 561 11 24 192 242 286 447:708 860 937 561 11 24 192 242 286 447 561:860 937 708 11 24 192 242 286 447 561 708:937 860 11 24 192 242 286 447 561 708 860:937 11 24 192 242 286 447 561 708 860 937 |
Довольно простая модификация обменной сортировки выборкой предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума и обмен их с первым и с последним элементами множества соответственно. Хотя итоговое количество сравнений и пересылок в этой модификации не уменьшается, достигается экономия на количестве итераций внешнего цикла.
Приведенные выше алгоритмы сортировки выборкой практически нечувствительны к исходной упорядоченности. В любом случае поиск минимума требует полного просмотра входного множества. В обменном варианте исходная упорядоченность может дать некоторую экономию на перестановках для случаев, когда минимальный элемент найден на первом месте во входном множестве.
ПУЗЫРЬКОВАЯ СОРТИРОВКА. Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного такого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходное множество, таким образом, формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.
Порядок пузырьковой сортировки - O(N2). Среднее число сравнений - N*(N-1)/2 и таково же среднее число перестановок, что значительно хуже, чем для обменной сортировки простым выбором.
Однако, то обстоятельство, что здесь всегда сравниваются и перемещаются только соседние элементы, делает пузырьковую сортировку удобной для обработки связных списков. Перестановка в связных списках также получается более экономной.
Еще одно достоинство пузырьковой сортировки заключается в том, что при незначительных модификациях ее можно сделать чувствительной к исходной упорядоченности входного множества. Рассмотрим некоторые их таких модификаций.
Во-первых, можно ввести некоторую логическую переменную, которая будет сбрасываться в false перед началом каждого прохода и устанавливаться в true при любой перестановке. Если по окончании прохода значение этой переменной останется false, это означает, что менять местами больше нечего, сортировка закончена. При такой модификации поступление на вход алгоритма уже упорядоченного множества потребует только одного просмотра.
Во-вторых, может быть учтено то обстоятельство, что за один просмотр входного множества на свое место могут "всплыть" не один, а два и более элементов. Это легко учесть, запоминая в каждом просмотре позицию последней перестановки и установки этой позиции в качестве границы между множествами для следующего просмотра. Именно эта модификация реализована в программной иллюстрации пузырьковой сортировке в примере 3.9. Переменная nn в каждом проходе устанавливает верхнюю границу входного множества.
|
|
|
В переменной x запоминается позиция перестановок и в конце просмотра последнее запомненное значение вносится в nn. Сортировка закончена, когда верхняя граница входного множества станет равной 1.
{===== Программный пример 3.9 =====}
Procedure Sort(var a: seq);
Var nn, i, x: integer;
begin nn:=N; { граница входного множества }
repeat x:=1; { признак перестановок }
for i:=2 to nn do { перебор входного множества }
if a[i-1]>a[i] then begin { сравнение соседних эл-в }
x:=a[i-1]; a[i-1]:=a[i]; a[i]:=x { перестановка }
x:=i-1; { запоминание позиции }
end; nn:=x; { сдвиг границы }
until (nn=1); {цикл пока вых. множество не захватит весь мас.}
end;
Результаты трассировки программного примера 3.9 представлены в таблице 3.6.
Таблица 3.6
| Шаг | nn | Содержимое а |
| исходный Результат | 717 473 313 160 949 764 34 467 757 800: 473 313 160 717 764 34 467 757 800:949 313 160 473 717 34 467 757:764 800 949 160 313 773 34 467:717 757 764 800 949 160 313 34 467:473 717 757 764 800 949 160 34:313 467 473 717 757 764 800 949 34:160 313 467 473 717 757 764 800 949 : 34 160 313 467 473 717 757 764 800 949 |
Еще одна модификация пузырьковой сортировки носит название шейкер-сортировки. Суть ее состоит в том, что направления просмотров чередуются: за просмотром от начала к концу следует просмотр от конца к началу входного множества. При просмотре в прямом направлении запись с самым большим ключом ставится на свое место в последовательности, при просмотре в обратном направлении - запись с самым маленьким. Этот алгоритм весьма эффективен для задач восстановления упорядоченности, когда исходная последовательность уже была упорядочена, но подверглась не очень значительным изменениям. Упорядоченность в последовательности с одиночным изменением будет гарантированно восстановлена всего за два прохода.
СОРТИРОВКА ШЕЛЛА. Это еще одна модификация пузырьковой сортировки. Здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д.
|
|
|
Последняя пузырьковая сортировка выполняется при d=1. Качественный порядок сортировки Шелла остается O(N2), среднее же число сравнений, определенное эмпирическим путем - log2(N2*N). Ускорение достигается за счет того, что выявленные "не на месте" элементы при d>1, быстрее "всплывают" на свои места.
Пример 3.10 иллюстрирует сортировку Шелла.
{===== Программный пример 3.10 =====}
Procedure Sort(var a: seq);
Var d, i, t: integer;
k: boolean; { признак перестановки }
begin d:=N div 2; { начальное значение интервала }
while d>0 do begin { цикл с уменьшением интервала до 1 }
k:=true; { пузырьковая сортировка с интервалом d }
while k do { цикл, пока есть перестановки }
begin k:=false; i:=1;
for i:=1 to N-d do {сравнение эл-тов на интервале d
begin if a[i]>a[i+d] then
begin t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; {перестановка }
k:=true; { признак перестановки }
end; { if... } end; { for... } end; { while k }
d:=d div 2; { уменьшение интервала }
end; { while d>0 } end;
Результаты трассировки программного примера 3.10 представлены в таблице 3.7.
Таблица 3.7
| Шаг | d | Cодержимое массива а |
| исходный результат | 76 22 4 17 13 49 4 18 32 40 96 57 77 20 1 52 32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52 32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52 13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57 13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57 1 17 13 20 4 18 32 22 4 40 76 49 77 52 96 57 1 17 4 18 13 20 4 22 32 40 76 49 77 52 96 57 1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57 1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57 1 4 17 4 18 13 20 22 32 40 49 76 52 77 57 96 1 4 4 17 13 18 20 22 32 40 49 52 76 57 77 96 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96 |
Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения.
Но сортировка требует еще и в среднем N2./4 перемещений, что делает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.
Алгоритм сортировки простыми вставками иллюстрируется программным примером 3.11.
{===== Программный пример 3.11 =====}
Procedure Sort(a: Seq; var b: Seq);
Var i, j, k: integer;
begin
for i:=1 to N do { перебор входного массива }
{ поиск места для a[i] в выходном массиве }
begin j:=1; while (j<i) and (b[j]<=a[i]) do j:=j+1;
{ освобождение места для нового эл-та}
for k:=i downto j+1 do b[k]:=b[k-1];
b[j]:=a[i]; { запись в выходной массив }
end; end;
Эффективность алгоритма может быть несколько улучшена при применении не линейного, а дихотомического поиска. Однако, следует иметь в виду, что такое увеличение эффективности может быть достигнуто только на множествах значительного по количеству элементов объема. Но поскольку алгоритм требует большого числа пересылок, то при значительном объеме одной записи эффективность может определяться не количеством операций сравнения, а количеством пересылок. Алгоритм обменной сортировки простыми вставками отличается от базового алгоритма только тем, что входное и выходное множество будут разделять одну область памяти.
ПУЗЫРЬКОВАЯ СОРТИРОВКА ВСТАВКАМИ. Это модификация обменного варианта сортировки. При такой сортировке входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее части. В исходном состоянии можно считать, что первый элемент последовательности уже принадлежит упорядоченному выходному множеству, остальная часть последовательности - неупорядоченное входное. Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное - уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного. Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности.
Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества "выплывает" на свое место в множестве. Поскольку при этом перестановка приводит к сдвигу нового в выходном множестве элемента на одну позицию влево, нет смысла всякий раз производить полный обмен между соседними элементами - достаточно сдвигать старый элемент вправо, а новый элемент записать в выходное множество, когда его место будет установлено. Именно так и построен программный пример пузырьковой сортировки вставками - 3.12.
{===== Программный пример 3.12 =====}
Procedure Sort (var a: Seq);
Var i, j, k, t: integer;
begin for i:=2 to N do { перебор входного массива }
{*** вх.множество - [i..N], вых.множество - [1..i] }
begin t:=a[i]; { запоминается значение нового эл-та }
j:=i-1; {поиск места для эл. в вых. множестве со сдвигом }
{конец цикла при достижении начала или, если найден эл.меньший}
нового} while (j>=1) and (a[j]>t) do
begin a[j+1]:=a[j]; { все эл-ты, большие нового сдвигаются}
j:=j-1; { цикл от конца к началу выходного множества }
end; a[j+1]:=t; { новый эл-т ставится на свое место }
end; end;
Результаты трассировки программного примера 3.12 представлены в таблице 3.8.
Таблица 3.8
| Шаг | Содержимое массива а |
| исходный результат | 48:43 90 39 9 56 40 41 75 72 43 48:90 39 9 56 40 41 75 72 43 48 90:39 9 56 40 41 75 72 39 43 48 90: 9 56 40 41 75 72 9 39 43 48 90:56 40 41 75 72 9 39 43 48 56 90:40 41 75 72 9 39 40 43 48 56 90:41 75 72 9 39 40 41 43 48 56 90:75 72 9 39 40 41 43 48 56 75 90:72 9 39 40 41 43 48 56 72 75 90: |
Хотя обменные алгоритмы стратегии включения и позволяют сократить число сравнений при наличии некоторой исходной упорядоченности входного множества, значительное число пересылок существенно снижает эффективность этих алгоритмов. Поэтому алгоритмы включения целесообразно применять к связным структурам данных, когда операция перестановки элементов структуры требует не пересылки данных в памяти, а выполняется способом коррекции указателей (см. главу 5).
Еще одна группа включающих алгоритмов сортировки использует структуру дерева.
