Сортировка массивов и файлов
Сортировкой базы данных называется переписывание записей базы данных в порядке, задаваемом при сортировке. В случае, когда наряду с базой данных поддерживается индекс базы данных, сортировка данных сводится к записи в выходной файл записей исходной базы данных в порядке, заданном индексом (смотри выше). Если нужный индекс не поддерживается, то можно его создать и далее поступить аналогичным образом. Однако зачастую это нужно сделать быстро, а сортировка на основе индексирования не оптимальна по времени. Существуют много других методов сортировки. Мы приведем несколько алгоритмов для того, чтобы проиллюстрировать методы программирования вообще и задач информатики в частности.
Все изложение будет вестись на примере массивов, однако реальные алгоритмы сортировки для файлов устроены аналогично. Все, что надо для сортировки массива - это для любых двух записей уметь определять, которая из записей должна быть расположена раньше, а какая позже. Поэтому методы сортировки мы будем иллюстрировать на примере сортировки массивов целых чисел.
Пусть задан массив a целых чисел длины n. Первый способ сортировки называется сортировкой обменом. Идея алгоритма достаточно проста. Найдем среди элементов массива минимальный и поменяем его с первым элементом, затем найдем минимальный среди оставшихся и поменяем его со вторым элементом и т.д. Фрагмент программы на Паскале выглядит так:
for
j:=1 to n-1 do {Для всех элементов массива, кроме последнего, сделать}
begin m := j; {Ищем минимальный элемент (вначале j-й) }
for k:=j+1 to n do
if a[k]<a[m] then m:=k; {Текущий минимальный элемент - k-й}
x := a[j]; {Обменять минимальный элемент с j-ым}
a[j] := a[m];
a[m] := x
end;
Второй способ сортировки называется пузырьковым. В первом цикле, начиная с первого, сравниваются соседние элементы массива, и они переставляются, если последующий элемент меньше предыдущего.
В конце цикла самый большой элемент автоматически оказывается в конце массива (“всплывает” в конец массива, отсюда название “пузырьковый”). Во втором цикле то же самое проделывается с элементами массива, исключая последний, и т.д. Фрагмент программы на Паскале выглядит так:
for
j:=n downto 2 do {Для всех начальных частей массива сделать}
for
k:=1 to j-1 do {Сравнить все пары соседних элементов от первого до (j-1)-го}
if a[k]>a[k+1]
begin x := a[k]; {Обменять k-й элемент с (k+1)-ым}
a[k] := a[k+1];
a[k+1]:= x
end;
Третий способ сортировки называется сортировкой слиянием. Пусть массив a длины n и массив b
длины m уже отсортированы в возрастающем порядке, и пусть мы хоти молучить массив длины (n+m), состоящий из их объединения и также отсортированный. Это делается за один проход по массиву a и массиву b
следующим образом:
j:=1; k:=1; i:=1; {Текущими являются первые элементы массивов a, b и c}
while (j<=n) or (k<=m) do {Пока не кончатся оба массива}
begin
if (j<=n) and ((k>m) or
(a[j]<=b[k])) then
{Массив a не кончился, а массив b кончился, либо массив b не кончился и
текущий элемент массива a меньше или равен текущему элементу массива b}
begin c[i]:=a[j]; {Записываем в массив c элемент массива a}
j:=j+1; {Сдвигаем текущий элемент массива a}
l:=i+1 {Сдвигаем текущий элемент массива c}
end
else if (k<=m) and ((j>n) or
(a[j]>b[k])) then
{Массив b не кончился, а массив a кончился, либо массив a не кончился и
текущий элемент массива a больше текущего элемента массива b}
begin c[i]:=b[k]; {Записываем в массив c элемент массива b}
k:=k+1; {Сдвигаем текущий элемент массива b}
l:=i+1 {Сдвигаем текущий элемент массива a}
end
end;
Идея полного алгоритма сортировки массива слиянием заключается в следующем. Предположим для простоты, что длина массива равна степени двойки. Разобьем весь массив на пары соседних элементов и упорядочим каждку пару по возрастанию. Затем каждые две соседних пары сольем в одну упорядоченную четверку. В следующем цикле сольем каждые две соседних четверки в одну упорядоченную восьмерку и т.д. Для такого алгоритма необходима модификация описанной выше процедуры слияния, которая сливала бы два следующих друг за другом фрагмента одного массива и записывала результат в другой массив. Если длина массива не равна степени двойки, то сливаемые фрагменты массива могут иметь разную длину, но принципиально ничего не изменится.
Преимущество сортировки слиянием заключается в том, что один цикл слияния происходит за один проход всего массива и поэтому таким методом можно сливать не только массивы, но и большие файлы, списывая их фрагментами в массивы в оперативную память. Алгоритм при этом несколько усложняется, но принципиально остается тем же. Количество циклов при сортировке слиянием (число проходов по всему массиву или файлу) равно приблизительно log2n, где n - длина массива или файла.
Принципиально иной алгоритм сортировки основан на идее упорядочения массива по частям. Пусть m и M - минимальное и максимальное значения элементов массива. Положим b=(m+M)/2. Переставим элементы массива так, чтобы в начале шли ( в произвольном порядке) элементы, меньшие или равные b, а затем элементы большие b. Для этого будем двигаться одновременно с начала массива до элемента, большего b, и с конца массива до элемента, меньшего b. Как только мы их найдем, переставим эти элементы местами и начнем двигаться дальше. Процесс заканчивается тогда, когда мы встретимся где-то в середине массива. Соответствующий фрагмент программы на Паскале записывается так:
j:=1; k:=n; {Текущими являются первый и последний элементы массива}
while j<k do {Пока мы не встретимся в середине массива}
begin
while (j<k) and (a[j]<=b) do j:=j+1; { Дойти до номера j, для которого a[j]>b}
while (j<k) and (a[k]>b) do k:=k-1; {Дойти до номера k, для которого a[k]<=b}
if j<k then begin x := a[j]; {Поменять a[j] и a[k]}
a[j] :=a[k];
a[k]:=x
end
end;
После описанной процедуры осталось отсортировать отдельно первую часть массива (до конечного значения переменных j и k) и вторую часть массива. Для этого аналогичную процедуру нужно повторить для первой части массива и значения b1=(b+m)/2 и второй части массива и значения b2=(b+M)/2. Для полученных двух кусков первой и второй частей повторить то же самое и т.д. Процесс прекращается тогда, когда при делении образуются фрагменты массива длины 1. Конечно, процедуру нужно модифицировать таким образом, чтобы она умела разделять произвольные фрагменты массива с произвольным пороговым значением b.
Последний алгоритм, который мы здесь рассмотрим - это сортировка деревом. Предположим, что элементы массива размещены в вершинах бинарного дерева, то есть вершинами дерева будут номера элементов от 1
до n). Будем считать, что элемент a[k] подчиняет элементы a[2k] и a[2k+1] (если 2k+1 или 2k больше n, соответствующие стрелки в дереве отсутствуют). корнем дерева является элемент a[1]. Постараемся перестановками элементов добиться того, чтобы каждый отец был не меньше своих сыновей. Назовем такое дерево регулярным. Очевидно, максимальным в регулярном дереве является корень a[1]. Поменяем теперь элементы a[1]
и a[n] и будем рассматривать оставшуюся часть массива длины n-1. Эта часть не будет регулярным деревом, так как оно испорчено: одна из вершин (с номером n) выкинута, а ее значение перенесено в корень. Однако испорчено оно несильно и его можно быстро исправить: корень дерева нужно поменять местами с максимальным из его сыновей, этого сына - с максимальным из его сыновей и т.д., пока очередная вершина не окажется больше своих сыновей либо их не будет вовсе.
После этого в корне снова окажется максимальный элемент из оставшихся (n-1)-го, и его следует поменять с элементом a[n-1]. Производя подобную процедуру со все меньшими фрагментами массива, мы добьемся того, что массив будет весь отсортирован.
Приведем вспомогательную процедуру восстановления регулярности дерева в корне (k - длина еще не отсортированной части массива):
j :=
1; {дерево регулярно везде, кроме, возможно, вершины с номером j}
while ((2*j+1<= k) and
(a[2*j+1] > a[j])) or ((2*j <= k) and (a[2*j] > a[j])) do
if (2*j+1 <= k) and (a[2*j+1]>=a[2*j]) {Больше элемент a[2j+1]}
then begin x:=a[2*j+1]; {обменять местами a[j] и a[2j+1] }
a[2*j+1]:=a[j];
a[j] := x;
j := 2*j+1 {текущей будет вершина с номером 2j+1}
end
else begin x:=a[2*j]; {обменять местами a[j] и a[2j] }
a[2*j]:=a[j];
a[j] := x;
j := 2*j {текущей будет вершина с номером 2j}
end;
Возможно вместо указанного алгоритма использовать рекурсивную процедуру:
procedure
regul (j,k: integer); {Восстановить регулярность поддерева с корнем j в массиве длины k}
var i: integer;
begin
if 2*j> k then i:=0 {Вершина j не имеет подчиненных}
else
if 2*j= k then i:=2*j {Вершина j имеет одну подчиненную вершину 2j}
else {Вершина j имеет две подчиненные вершины 2j и 2j+1}
if a[2*j+1]>=a[2*j] {Выбрать максимальную из двух подчинееных вершин}
then i:=2*j+1
else i:= 2*j;
if (i>0) and (a[j]<a[i]) then {Вершина j не регулярная}
begin x := a[i]; {обменять местами a[j] и a[i] }
a[i] := a[j];
a[j] := x;
regul (i,k) {Рекурсивный вызов процедуры regul для того, чтобы восстановить
регулярность поддерева с корнем в вершине с номером i}
end
end;
Аналогичная процедура используется для того, чтобы сделать весь массив регулярным на начальной стадии сортировки. Мы не будем ее здесь приводить.
