Введение
Пусть M – это множество элементов, на котором задано отношение порядка, часто обозначаемое знаком £ (меньше или равно). Иногда это отношение называют отношением предшествования. Считается, что для любых двух элементов x и y этого множества выполняется x £ y или y £ x, при этом не запрещается одновременное выполнение этих соотношений, но это не означает, что x и y один и тот же элемент. Считается, что это отношение транзитивно, то есть, если x £ y и y £ z, то x £ z. В математике такое отношение называется линейным квазипорядком.
Если, например M это множество учеников класса, то их можно упорядочить по росту или по весу или по баллу успеваемости. В этих случаях вес, рост, балл успеваемости представляется в каком-либо числовом формате и используется для проверки условия.
Например, если M - это множество слов, составленных из букв некоторого алфавита, то M можно упорядочить в так называемом алфавитном порядке.
Множество, каждому элементу которого приписана числовая характеристика, называется «взвешенным» множеством. В нашем примере это вес, рост, учебный балл. Характеристика, приписанная элементу, часто называется его весом или ключом. При рассмотрении взвешенных множеств ключ элемента x часто обозначают выражением key(x), а отношение порядка при этом индуцировано ключом.
Под задачей сортировки (или задачей упорядочения) множества M понимают следующее. Требуется представить M в виде последовательности его элементов, так чтобы для любых двух подряд идущих элементов x и y выполнялось соотношение x £ y. Для взвешенных множеств это будет равносильно числовому неравенству key(x) £ key(y).
Уточнения этой задачи связаны с теми средствами, с помощью которых предполагается ее решение. Нас интересуют алгоритмы с точки зрения их компьютерной реализации. При этом существенным является вопрос о том, как представлено исходное множество в памяти компьютера и каким образом должен быть представлен результат сортировки.
В простейшем случае будем считать, что множество, состоящее из n элементов, представлено в виде массива длины n. В каждом элементе массива закодирован элемент множества. Полагаем, что в нашем распоряжении есть процедура, позволяющая проверять истинность соотношения (x £ y). При работе с взвешенным множеством можно полагать, что оно представлено двумя синхронными массивами a[1..n] и key[1..n]. В массиве a будут расположены сами элементы или ссылки на них, а в числовом массиве key ключи соответствующих элементов. В обоих случаях задачу будем называть задачей сортировки массива.
Большинство алгоритмов, осуществляющих сортировку массивов, основано на целенаправленном сравнении пар элементов и в случае необходимости, их перемещении в массиве, так чтобы в итоге массив оказался упорядоченным в соответствии с критерием сортировки.
Существует большое количество различных стратегий, в соответствии с которыми может осуществляться перестановка элементов массива. При описании таких стратегий будем рассматривать задачу сортировки массива в следующей упрощенной форме. Задан числовой массив a[1..n], требуется переставить его элементы, то есть обменять содержимое элементов массива, так чтобы в результате перестановок выполнилось условие: a[1] £ a[2] £ ... £ a[n].
Во многих представленных ниже алгоритмах нам потребуется операция перестановки местами двух элементов массива. Ее можно выполнить с помощью трех операторов присваивания. Чтобы поменять местами содержимое переменных a[i] и a[j] будем использовать процедуру транспонирования
tr(i,j),
заключающуюся в выполнении следующих трех операторов:
temp:=a[i]; a[i]:=a[j]; a[j]:=temp.
При работе с взвешенными множествами, представленными, как говорилось выше, двумя синхронными массивами a[1..n] и key[1..n] придется менять местами элементы как в массиве a, так и в массиве key.
Оценивая качество различных алгоритмов, обычно интересуются тем, как зависит время его работы от длины n сортируемой последовательности и требуется ли для этого дополнительная память, размер которой зависит от параметра n.
В прикладных задачах операции сравнения пары элементов и их перемещения могут иметь разную трудоемкость. Если, например, операция перемещения требует намного больше времени чем операция сравнения, то выбирается стратегия, требующая меньше перемещений, в противном случае – стратегия, требующая меньше сравнений.
Поскольку время работы таких алгоритмов существенно зависит от количества сравнений и перемещений элементов в массиве, следует обращать внимание на то, как эти количества зависят от длины сортируемого массива.
Часть наших стратегий можно назвать пузырьковыми, они характеризуются тем, что «легкие» (то есть меньшие элементы) целенаправленно перемещаются в направлении к началу массива, а более «тяжелые» - к концу массива. Описанную выше задачу называют задачей сортировки по неубыванию. Все представленные ниже алгоритмы легко модифицировать для задачи сортировки по невозрастанию.
При представлении алгоритмов в качестве псевдо кода будем использовать фрагменты языка Паскаль с некоторыми отступлениями. В частности будем опускать описательную часть, когда она ясна из контекста. Операторные скобки begin и end будем иногда заменять фигурными, особенно когда они находятся в одной строчке. Также в текст алгоритма будем в качестве операторов вставлять фразы на естественном языке, когда их реализация на формальном языке очевидна.
1. Пузырьковые стратегии
1.1. Традиционная пузырьковая сортировка.
Бесхитростный алгоритм сортировки числового массива a[1..n] состоящего из n элементов может заключаться в выполнении следующих операторов
for k:=1 to n-1 do
for i:=1 to n-k do
if a[i]<a[i+1] then tr(i,i+1);
Заметим, что после первого выполнения внутреннего цикла (при k = 1) на последнем месте в массиве a[1..n] окажется максимальный элемент этого массива. После второго его выполнении (при k = 2) на предпоследнем месте в массиве a[1..n] окажется элемент меньше или равен максимальному, но не меньше остальных и т.д. После последнего выполнения внутреннего цикла (при k = n-1) массив окажется полностью отсортированным.
Легко видеть, что при работе алгоритма будет выполнено ровно n (n – 1) / 2 сравнений «a[i] < a[i+1]», а суммарное число перемещений, выполненных в процедуре транспонирования, будет не более чем умноженное на 3 указанное число сравнений. Следует заметить, что этими подсчетами не ограничивается реальное число выполнений элементарных операций с памятью, поскольку организация циклов и обращений к процедуре транспонирования также требует скрытых от нас операций с памятью, зависящих от используемой системы программирования. Однако мы обоснованно можем считать, что эти накладные расходы не более чем в константное число раз превышают результаты наших подсчетов.
Не имея возможности оценивать упомянутые константы, при анализе сложности алгоритмов ограничиваются асимптотическими оценками. В нашем случае приведенные оценки числа сравнений и перемещений позволяют оценить время работы пузырьковой сортировки в худшем случае величиной O(n2).
1.2. Сортировка с экономией числа сравнений
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре нарушен, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
begin
t:= true;
while t do
begin
t:=false;
for j:=1 to n−1 do
if A[j]>A[j+1] then {tr(j,j+1);t:=true}
end
end.
Булева переменная t используется для того, чтобы определить, был ли произведён хотя бы один обмен на очередной итерации внешнего цикла. Алгоритм останавливается, когда таких обменов не было.
Алгоритм можно немного улучшить следующими способами:
- Внутренний цикл можно выполнять для j = 1, 2, ..., (n − i), где i − номер итерации внешнего цикла (нумерация с единицы), так как на i-ой итерации последние i элементов массива уже будут правильно упорядочены.
- Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой.
1.3. Сортировка с экономией числа перемещений
Заключается в выполнении следующих операторов.
for k:=1 to n-1 do for i:=k+1 to n do
if a[i]<a[k] then tr(i,k);
Заметим, что после первого выполнения внутреннего цикла (при k = 1) на первом месте в массиве a[1..n] окажется минимальный элемент массива. После второго его выполнения (при k = 2) на втором месте в массиве a[1..n] окажется элемент больше или равен первому, но не больше остальных и т.д., после последнего, т. е. (n-1)-го выполнении внутреннего цикла (при k = n-1) массив окажется полностью отсортированным.
Число сравнений "a[i] < a[k]" будет выполнено n(n – 1)/2, а число перемещений будет, как правило, меньше, но в худшем все равно получим асимптотическую оценку O(n2).
1.4. Сортировка вставками
Используем следующие соображения. Сегмент массива, состоящий из одного первого элемента, очевидно, следует считать упорядоченным. Предположим теперь, что первые k элементов массива уже упорядочены, тогда берем (k+1)-ый элемент и, сканируя массив от него влево, находим место для выбранного элемента среди первых k. Если такое место находится, то помещаем туда элемент, занимавший ранее (k+1)-e место.
Описанные действия можно реализовать операторами
for k:=2 to n do
begin
b:=a[k]; i:=k-1;
while (i>0)&(a[i]>b) do begin a[i+1]:=a[i]; i:=i-1 end;
a[i+1]:=b
end.
Время работы этого алгоритма как и многих других конечно зависит от величины n, но может быть разным и для массивов, состоящих из одного и того же количества элементов, в зависимости от степени упорядоченности этих последовательностей до начала сортировки. Так, если полученный на входе массив оказался уже упорядоченным, то время работы может быть оценено как O(n). В этом легко убедиться, заметив, что условие в цикле while при каждом значении k = 2, 3, …, n будет срабатывать не более одного раза. Если же исходный массив был упорядочен в обратном порядке, то мы вынуждены оценить время величиной O(n2). В частности это означает, что при увеличении длины массива в 2 раза время работы увеличивается в 4 раза.
2. Стратегии «разделяй и властвуй»
2.1. Традиционная стратегия
Предположим, что в нашем распоряжении имеется процедура
SPLIT(i,j,k),
которая по заданным значениям индексов i, j находит некоторое промежуточное значение k и переставляет элементы сегмента a[i..j] так, чтобы для s = i, i + 1, ..., k – 1 выполнялось неравенство a[s] £ a[k], а для s = k + 1, k + 2, ..., j - неравенство a[k] £ a[s].
Тогда для сортировки сегмента a[i .. j] может быть использована следующая рекурсивная процедура.
procedure SORT(i,j);
begin if i=j then exit
else begin SPLIT(i,j,k); SORT(i,k–1); SORT(k+1,j)end
end;
Для сортировки всего исходного массива достаточно выполнить оператор
SORT(1,n).
Заметим, что если бы процедура SPLIT работала линейное от длины сегмента время и давала значение k, близкое к середине между i и j, то число обращений к ней приблизительно равнялось бы log n и сортировка всего массива проходила бы за время порядка O(n×log n). Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения
- Разработайте вариант процедуры без использования рекурсии. Сколько дополнительной памяти требуется для запоминания границ еще не отсортированных сегментов?
- Охарактеризуйте работу процедуры SORT на заранее отсортированном массиве.
- Напишите на известном вам алгоритмическом языке программу сортировки числового массива с помощью процедуры SORT и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел. Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
2.2. Сортировка слиянием
Этот метод является разновидностью метода «разделяй и властвуй», впрочем, уместнее его было бы назвать «властвуй и объединяй».
Предположим, что у нас есть процедура
MERGE(i, j, k),
которая два уже отсортированных сегмента a[i..(j – 1)] и a[j..k] преобразует (сливает) в один сегмент a[i..k], делая его полностью отсортированным. Тогда рекурсивная процедура
procedure MergSort(i,j);
begin
if i=j then exit else
begin
m:=(i+j)div 2; SORT(i,m); SORT(m+1,j); MERGE(i,m,j)
end
end;
очевидно, сортирует сегмент a[i .. j], а для сортировки всего исходного массива достаточно выполнить оператор
MergSort(1,n).
Как видим, вопрос балансировки размера сегментов решается здесь просто делением пополам. Число обращений к процедуре MERGE примерно равно log n, а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
2.3. Демонстрационная программа MergeSort
Приведенная ниже программа MergeSort генерирует псевдослучайный массив длины n = 30, печатает его, сортирует методом слияния и печатает результат сортировки. Вспомогательная процедура Merge сливает сегменты a[L..mid] и a[mid+1..L] массива a в сегмент b[L..R] массива b. Затем b[L..R] копируется в соответствующий сегмент массива a.
Program MergeSort; const n=30;
Var a,b: array[1..n] of integer; k:integer;
Procedure Merge(L,R: integer); Var mid,i,j,k: integer;
Begin
mid:=(L+R) div 2; i:=L; j:=mid+1;
for k:=L to R do
if (i<=mid)and((j>R) or (a[i]<a[j]))
then begin b[k]:=a[i]; i:=i+1 end
else begin b[k]:=a[j]; j:=j+1 end;
for k:=L to R do a[k]:=b[k];
End;
Procedure Sort(L,R: integer);
Begin
if L<R then
begin
Sort(L,(L+R)div 2); Sort((L+R)div 2+1,R);
Merge(L,R)
end
End;
Begin randomize;
for k:=1 to n do a[k]:=random(100);
for k:=1 to n do write(a[k]:3); writeln;
Sort(1,N);
for k:=1 to n do write(a[k]:3); writeln;
End.
Большим недостатком сортировки слиянием является расход вспомогательной памяти. В приведенной программе его требует массив b и скрытая реализация рекурсивного исполнения процедуры Sort. Математический анализ дает оценку трудоемкости O(n log n). За счет небольшого усложнения логики программы нетрудно вдвое сократить расход памяти под массив b.
2.4. Быстрая сортировка
Суть алгоритма заключается в следующем. В массиве выбирается произвольный элемент х. Мы будем выбирать последний элемент массива. Заметим, что способ выбора элемента x не влияет на корректность приводимого ниже алгоритма. Сканированием массива от первого элемента вправо отыскивается первый попавшийся элемент, который больше х, а от последнего элемента влево первый попавшийся элемент, который меньше х. Найденные элементы меняются местами и сканирование продолжается. Когда оказываются просмотренными все элементы массива, элемент x записывается на место так чтобы все элементы, которые оказались слева от х были меньше или равны х, а все элементы, которые оказались справа от х были больше или равны х. Далее с сегментами массива слева и справа от x поступают точно также. Продолжая деление этих сегментов до тех пор, пока не останется в них по одному элементу, в результате получим полностью отсортированный массив.
В алгоритме используется процедура-функция,
Function Part(L,R),
которая в соответствии с выше описанным по заданным значениям индексов L, R (L < R) выдает значение индекса k = Part(L, R), такое, что L £ k £ R и для s = L, L + 1, ..., k – 1 справедливы неравенства a[s] £ a[k], а для s = k+1, k+2, ..., R - неравенства a[k] £ a[s].
Эта процедура может быть реализована следующим образом.
function Part(L,R:integer):integer;
var x,i,j: integer;
begin x:=a[R]; i:=L-1;
for j:=L to R-1 do
if a[j]<=x then begin i:=i+1; tr(i,j) end;
tr(i+1,R);
Part:=i+1
end;
Рекурсивная процедура
QSort(L,R),
осуществляющая быструю сортировку сегмента a[L..R] массива a может быть реализована операторами
if L<R then
begin
mid:=part(L,R); QuickSort(L,mid-1); QuickSort(mid+1,R)
end;
Чтобы отсортировать исходный массив a[1..n] достаточно выполнить оператор
QSort(1,n)
Математический анализ трудоемкости алгоритма QuickSort показывает, что оценка худшего случая является величиной O(n2), оценка среднего случая O(n log n).
2.5. Демонстрационная программа QuickSort
Приведенная ниже программа QuickSort генерирует с помощью датчика псевдослучайных чисел массив длины n = 30, печатает его, сортирует методом быстрой сортировки и печатает результат сортировки.
program Qsort; Const N=30;
var a: array[1..n] of integer; k: integer;
function PARTITION(L,R:integer):integer;
var mid,x,j: integer;
begin mid:=R;x:=a[mid]; j:=L;
While j<mid do
if a[j]<x then j:=j+1 else
begin
a[mid]:=a[j]; mid:=mid-1; a[j]:=a[mid]; a[mid]:=x
end;
PARTITION:=mid
end;
procedure QuickSort(L,R:integer); var mid: integer;
begin
if l<r then
begin mid:= PARTITION(L,R);
QuickSort(L,mid-1); QuickSort(mid+1,R)
end;
end;
begin
for k:=1 to n do a[k]:=random(100);
for k:=1 to n do write(a[k]:3); writeln;
QuickSort(1,n);
for k:=1 to n do write(a[k]:3); writeln;
end.
2.6. Поиск к-ой порядковой статистики
K-ой порядковой статистикой набора из n чисел называется элемент, который после сортировки набора в возрастающем прядке оказывается на к-ом месте. В частности первая порядковая статистика равна минимальному элементу массива и может быть найдена сканированием массива за время O(n). Однако при произвольном k не столь очевидно как с такой трудоемкостью в худшем случае найти k-ую порядковую статистику. Для этой цели существует достаточно хитроумный алгоритм (см., например, [1]).
Конечно, k-ую порядковую статистику можно найти за время O(1) предварительно отсортировав массив по возрастанию, а затем выбрав k-ый по счету элемент. Однако предварительная сортировка требует времени W(n log n).
Ниже мы рассмотрим алгоритм, который лишь в среднем за время O(n) решает поставленную задачу. Идея этого алгоритма вытекает из рассмотренного выше алгоритма QuickSort и заключается в следующем. Используемая в нем процедура Partition разбивает массив на левый и правый сегменты, которые в дальнейшем рекурсивно обрабатываются, однако если нам нужна лишь k-ая статистка мы легко определяем, в каком сегменте находится нужный нам элемент.
Действительно, пусть при очередном разбиении разделяющий элемент оказался в позиции mid. Тогда в случае k = mid очевидно k-ой порядковой статистикой будет элемент a[mid]. Если k < mid, то рекурсивно ищем k-ую статистику в левом сегменте массива. Если же k > mid, то рекурсивно ищем (k-mid-1)-ую статистику в его правом сегменте.
Ниже представлена процедура-функция GetOrdSt(L, R, k) поиска k-ой порядковой статистики, в сегменте a[L..R] массива a, использующая ту же самую процедуру Partition, что и в алгоритме QuickSort.
function GetOrdSt(L,R,k:integer):integer;
var mid,k1:integer;
begin
mid:=PARTITION(L,R); k1:=mid-L+1 ;
if k=k1 then GetOrdSt:=A[mid]
else if k<k1 then GetOrdSt:=GetOrdSt(L,mid-1,k)
else GetOrdSt:=GetOrdSt(mid+1,R,k-k1)
end;
Математический анализ времени работы алгоритма показывает, что его можно оценить величиной O(n) лишь в среднем случае. Может возникнуть худший случай, в котором процедура partition каждый раз будет возвращать левую или каждый раз правую границу рассматриваемого сегмента. В таком случае время работы составит W(n2).
Однако существуют, как мы уже говорили достаточно хитроумные алгоритмы, которые оцениваются также величиной O(n) но уже в худшем случае.
2.7. Демонстрационная программа OrderStatistic
Приведенная ниже программа OrderStatistik на языке Паскаль генерирует псевдослучайный массив длины n и находит все порядковые статистики от 1-ой до n-ой. Она это делает с помощью программы, полученной из программы QuickSort с помощью очевидной модификации.
program OrderStatistic; const n=30;
var a: array[1..n] of integer; s: integer;
function Partition(L,R:integer):integer;
var mid,x,j: integer;
begin mid:=R;x:=a[mid]; j:=L;
While j<mid do if a[j]<x
then j:=j+1
else
begin
a[mid]:=a[j]; mid:=mid-1; a[j]:=a[mid]; a[mid]:=x
end;
Result:=mid
end;
function GetOrdSt(L,R,k:integer):integer;
var mid,k1:integer;
begin
mid:=PARTITION(L,R); k1:=mid-L+1 ;
if k = k1 then GetOrdSt:=A[mid]
else if k<k1 then GetOrdSt:=GetOrdSt(L,mid-1,k)
else GetOrdSt:=GetOrdSt(mid+1,R,k-k1)
end;
begin
for s:=1 to n do a[s]:=random(100);
for s:=1 to n do write(a[s]:3); writeln;
for s:=1 to n do write(GetOrdSt(1,n,s):3); writeln;
end.
2.8. Двоичный поиск элемента в отсортированном массиве
Поиск нужного числа k в отсортированном числовом массиве a[1..n] осуществляется следующим образом. Число k сравнивается с числом, расположенным в середине массива a. В качестве такого числа выбирается элемент, находящийся в позиции M = (n +1) div 2. Если a[M] < k, то поиск продолжается в сегменте a[1..M-1], если a[M] > k, то в сегменте a[M+1..n]. Если a[M] = k, то искомое число обнаружено в позиции M. Таким образом, если число k присутствует в массиве, то оно будет обнаружено и в качестве ответа переменной ind присваивается номер позиции, в которой оно находится. В противном случае переменной ind присваивается число -1, как признак того, что числа k в нашем массиве нет.
Ниже приведена демонстрационная программа BinarySearch, которая генерирует псевдослучайный целочисленный массив a[1..n] длины n и случайное число k. Затем в массиве происходит поиск числа k. Если k присутствует в массиве, то будет напечатано сообщение, в какой позиции оно находится, если числа k в массиве нет, то об этом тоже будет напечатано соответствующее сообщение.
program BinarySearch; Const N=30;
var a:array[1..n] of integer; s,L,R,k,M,ind: integer;
procedure Search(k:integer; var ind:integer);
begin L:=1; R:=n;
while true do
begin
M:= (L+R) div 2;
if (K<a[M]) числа
then R:=M-1
else if (K>a[M])
then L:=M+1
else begin ind:=M; exit end;
if (L>R) then begin ind:=-1; exit end;
end;
end;
begin k:=random(15);
randomize; a[1]:=random(3);
for s:=2 to n do a[s]:=a[s-1]+random(3);
for s:=1 to n do write(a[s]:3); writeln;
Search(k,ind);
if ind=-1
then writeln('Число ',k,' отсутствует в массиве')
else writeln('Число ',k,' находится в позиции ',ind)
end.
2.9. Сортировка подсчетом
В сортировке подсчетом (counting sort) предполагается, что исходный массив a[1..n] содержит целые числа из интервала 0..k, где k - некоторая целая константа. Если k = О(n), то время работы алгоритма сортировки подсчетом равно Q(n).
Путем однократного сканирования массива a формируется вспомогательный массив c[0..k], в котором с[i] равно количеству таких позиций j массива a, в которых a[j]£i. Например, c[0] – это количество нулей в массиве a, c[1] – количество нулей и единиц и т. д. Массив c очевидно можно сформировать с помощью следующих операторов.
for i:=0 to k do c[i]:=0;
for j:=1 to n do c[a[j]]:=c[a[j]]+1;
for i:=1 to k do c[i]:=c[i]+c[i-1];
После того как массив c сформирован остается перенести элементы из исходного массива a в результирующий массив b, в котором элементы сразу будут вставать на свои места. Это можно осуществить с помощью оператора
for j:=n downto 1 do
begin b[c[a[j]]]:=a[j]; c[a[j]]:=c[a[j]]-1 end;
Поясним, например, на первом витке цикла элемент a[n] переместится в b[a[n]], а c[a[n]] уменьшится на единицу, чтобы на следующем витке элемент a[n-1] попал в нужное место и т.д.
Сколько времени требуется для сортировки методом подсчета? На формирование массива c, учитывая, что k = О(n), очевидно требуется время Q(n). Операци перемещения элементов массива a в массив b также требуется время Q(n). Итак, итоговая оценка Q(n).
Известно, что нижняя оценка времени сортировки алгоритмами, использующими сравнения, равна W(n log n). Как же нам удалось получить W(n). Ответ в том, что мы сузили задачу, предположив, что k = О(n).
Важное свойство алгоритма сортировки подсчетом заключается в том, что он устойчив. Это означает, что элементы с одним и тем же ключом находятся в выходном массиве в том же порядке, что и во входном. Обычно свойство устойчивости важно в ситуации, когда сортируемые элементы имеют сопутствующие данные. Устойчивость, присущая сортировке подсчетом, важна еще и по другой причине: этот алгоритм часто используется в качестве подпрограммы при поразрядной сортировке.
В следующем разделе увидим, что устойчивость сортировки подсчетом гарантирует корректную работу поразрядной сортировки.
2.10. Демонстрационная программа сортировки подсчетом
Приведенная ниже программа CountingSort на языке Паскаль генерирует массив a[1..30], элементы которого псевдослучайные числа в интервале 0..99. Затем сортирует его, используя вспомогательный массив c, методом подсчета, получая результирующий массив b. Заметим, что массив a остается неизменным.
Program CountingSort; const n=30; k=99;
Var a,b: array[1..n] of integer; c: array[0..k] of integer; i,j:integer;
begin
for i:=1 to n do a[i]:=random(k);
for i:=1 to n do write(a[i]:3); writeln;
for i:=0 to k do c[i]:=0;
for j:=1 to n do c[a[j]]:=c[a[j]]+1;
for i:=1 to k do c[i]:= c[i]+c[i-1];
for j:=n downto 1 do
begin b[c[a[j]]]:=a[j]; c[a[j]]:=c[a[j]]-1 end;
for i:=1 to n do write(b[i]:3); writeln;
end.
2.11. Поразрядная сортировка
В поразрядной сортировке (radix sort) предполагается, что ключи представляют собой натуральные числа фиксированной разрядности d, например, в десятичной системе счисления. Сама сортировка осуществляется в d этапов. Сначала массив сортируется по младшему разряду, затем по следующему по старшинству разряду и т.д. до тех пор, пока не будут исчерпаны все d разрядов. Если сортировка по каждому разряду обладает свойством устойчивости, то и в целом поразрядная сортировка будет обладать этим свойством.
Идея поразрядной сортировки иногда применяется для приведения в порядок записей, ключи которых разбиты на несколько полей. Например, пусть нужно выполнить сортировку дат по трем ключам: год, месяц и день. Для этого можно было бы запустить алгоритм сортировки с функцией сравнения, в котором в двух заданных датах сначала бы сравнивались годы, при их совпадении сравнивались месяцы, а при совпадении и тех, и других сравнивались бы дни. Можно поступить и по-другому, то есть выполнить трехкратную сортировку с помощью устойчивой процедуры: сначала по дням, потом по месяцам и наконец, по годам.
2.12. Внешняя сортировка
Внешней сортировкой называют сортировку данных располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в оперативную память и применить один из методов внутренней сортировки.
Внешняя память характеризуется последовательным доступом к элементам данных в отличие от прямого (адресуемого) доступа к данным во внутренней (оперативной) памяти. Методы внешней сортировки появились, когда устройствами внешней памяти были магнитные ленты с чисто последовательным доступом. Современные дисковые запоминающие устройства реализуют так называемый индексно-последовательный доступ, при котором время обращения к данным состоит из двух этапов: практически прямого доступа к блоку памяти и затем последовательного считывания данных из выбранного блока во внутреннюю память. Эти особенности работы с внешней памятью естественно следует учитывать при разработке алгоритмов.
Следует заметить, что скорость выполнения алгоритмов зависит от размера блоков, которые способна принять внутренняя память. Мы рассмотрим метод внешней сортировки, работающие при минимальных расходах оперативной памяти.
Посмотрим, как можно использовать метод слияния при внешней сортировке. Предположим, что в файле A, записаны последовательно элементы сортируемого числового массива a[1..n]. Для простоты предположим, что n представляет собой степень числа 2. Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки. Для сортировки используются два вспомогательных файла B и C. Размер каждого из них будет n/2.
Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение содержимого файла A в файлы B и C, а затем слияние файлов B и C в файл A.
На первом шаге последовательно читается файл A, из которого записи с нечетными номерами a[1], a[3], ..., a[n-1] переписываются в файл B, а записи a[2], a[4], ..., a[n] с четными номерами – в файл C. Первое слияние производится над парами (a[1], a[2]), (a[3], a[4]), ..., (a[n-1], a[n]), в результате чего каждая пара оказывается упорядоченной по неубыванию и эти пары последовательно записываются в файл A.
На втором шаге из файла A последовательно переписываются в файл B уже пары с нечетными номерами, а пары с четными номерами, а в файл C. При очередном слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей.
Заметим, что для выполнения внешней сортировки методом слияния в основной памяти требуется расположить всего лишь две переменные – для размещения очередных записей из файлов B и C. Файлы A, B и C будут O(log n) раз прочитаны и столько же раз записаны.