Основы дискретной математики (стр. 5 из 23)
for k:=1 to N do begin write ('Bведитеэлементa [', k, ']=');
readln (a[k]);
end;
for k:=1 to N do begin write (a[k], ' ');
end;
writeln;
(*алгоритм сортировки с помощью дерева*)
(*построениепирамиды*)
L:=(n div 2) +1; R:=n; while L>1 do begin L:=L‑1; SIFT (L, R);
end;
(*сортировка*)
while R>1 do begin x:=a[l]; a[l]:=a[R]; a[R]:=x; R:=R‑1; SIET (1, R);
end;
(*выводотсортированногомассива*) for k:=1 to N do begin write (a[k], ' ');
end;
readln;
end.
Сортировка с помощью обменов
1‑ый вариант. Соседние элементы массива сравниваются и при необходимости меняются местами до тех пор, пока массив не будет полностью упорядочен. Повторные проходы массива сдвигают каждый раз наименьший элемент оставшейся части массива к левому его концу. Метод широко известен под названием «пузырьковая сортировка» потому, что большие элементы массива, подобно пузырькам, «всплывают» на соответствующую позицию. Основной фрагмент программы содержит два вложенных цикла, причём внутренний цикл удобнее выбрать с шагом, равным -1 [8]:
for i: =2 to n do
for j:=n downto i do
if a [j‑1]>a[j] then
begin {обмен}x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=xend;
2‑ой вариант. Пузырьковая сортировка является не самой эффективной, особенно для последовательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из которых один берется слева (i = 1), другой – справа (j = n). Если a[i] <= a[j], то устанавливают j = j – 1 и проводят следующее сравнение. Далее уменьшают j до тех пор, пока a[i] > a[j]. В противном случае меняем их местами и устанавливаем i = i + 1. Увеличение i продолжаем до тех пор, пока не получим a[i] > a[j]. После следующего обмена опять уменьшаем j. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i = j. После этого этапа возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него младшие элементы, а справа – старшие [8].
Далее подобную процедуру можно применить к левой и правой частям массива и т. д. Очевидно, что характер алгоритма рекурсивный. Для запоминания ведущих левого и правого элементов в программе необходимо использовать стек.
Характерной чертой алгоритмов сортировки с помощью обмена является обмен местами двух элементов массива после их сравнения друг с другом. В так называемой «пузырьковой сортировке» проводят несколько проходов по массиву, в каждом из которых повторяется одна и та же процедура: сравнение двух последовательно стоящих элементов и их обмен местами в порядке меньшинства (старшинства). Подобная процедура сдвигает наименьшие элементы к левому концу массива.
program sortirovka_6;
(*сортировка прямым обменом – пузырьковая сортировка*)
const N=5;
type item= integer;
var a: array [1..n] of item; i, j: integer; x: item;
begin (*заданиеискомогомассива*)
for i:=1 to N do begin write ('введиэлементa [', i, ']= ');
readln (a[i]);
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм пузырьковой сортировки*)
for i:=2 to n do for j:=n downto i do begin
if a [j‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x;
end;
end;
(*вывод отсортированного массива*)
for i:=1 to N do begin write (a[i], ' ');
end;
readln;
end.
Представленную программу можно легко улучшить, если учесть, что если после очередного прохода перестановок не было, то последовательность элементов уже упорядочена, т. е. продолжать проходы не имеет смысла. Если чередовать направление последовательных просмотров, алгоритм улучшается. Такой алгоритм называют «шейкерной» сортировкой.
program sortirovka_7;
(*сортировка прямым обменом – шейкерная сортировка*)
const N=5;
type item= integer;
var a: array [1..n] of item; i, j, k, L, R: integer; x: item;
begin (*заданиеискомогомассива*)
for i: =1 to N do begin write ('введиэлемента [', i, '] = ');
readln (a[i]);
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм шейкерной сортировки*)
L: =2; R:=n; k:=n;
repeat
for j:=R downto L do begin
if a [j-l]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j];
a[j]:=x; k:=-j
end;
end;
L:=k+1;
for j:=L to R do begin
if a [j-l]>a[j] then begin x:=a [j-l]
a [j-l]:=a[j]; a[j]:=x; k:=j
end;
end;
R:=k‑1; until L>R;
(*вывод отсортированного массива*)
for i:=l to N do
begin write (a[i], ' ');
end;
readln;
end.
Быстрая сортировка
Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки – быстрая сортировка, предложенная Ч. Хоаром. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort [6].
Этому методу требуется O (nlog2n) в среднем и O(n2) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т. е. он не является и методом сортировки на месте.
Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции Partition один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального, следует расположить слева от него, те, которые больше – справа.
int function Partition (Array A, int Lb, int Ub);
begin
select a pivot from A[Lb]… A[Ub];
reorder A[Lb]… A[Ub] such that:
all values to the left of the pivot are £ pivot
all values to the right of the pivot are ³ pivot
return pivot position;
end;
procedure QuickSort (Array A, int Lb, int Ub);
begin
if Lb < Ub then
M = Partition (A, Lb, Ub);
QuickSort (A, Lb, M – 1);
QuickSort (A, M + 1, Ub);
end;
На рисунке 1.11 (а) в качестве центрального выбран элемент 3. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами – см. рисунок 1.11 (b). Процедура QuickSort рекурсивно сортирует два подмассива, в результате получается массив, представленный на рисунке 1.11 (c).
В процессе сортировки может потребоваться передвинуть центральный элемент. Если нам повезет, выбранный элемент окажется медианой значений массива, т. е. разделит его пополам. Предположим на минутку, что это и в самом деле так. Поскольку на каждом шаге мы делим массив пополам, а функция Partition, в конце концов, просмотрит все n элементов, время работы алгоритма есть O (nlog2n).
В качестве центрального функция Partition может попросту брать первый элемент (A[Lb]). Все остальные элементы массива мы сравниваем с центральным и передвигаем либо влево от него, либо вправо. Есть, однако, один случай, который безжалостно разрушает эту прекрасную простоту. Предположим, что наш массив с самого начала отсортирован. Функция Partition всегда будет получать в качестве центрального минимальный элемент и потому разделит массив наихудшим способом: в левом разделе окажется один элемент, соответственно, в правом останется Ub – Lb элементов.
Рисунок 1.11 – Пример работы алгоритма Quicksort
Таким образом, каждый рекурсивный вызов процедуры quicksort всего лишь уменьшит длину сортируемого массива на 1. В результате для выполнения сортировки понадобится n рекурсивных вызовов, что приводит к времени работы алгоритма порядка O(n2). Один из способов побороть эту проблему – случайно выбирать центральный элемент. Это сделает наихудший случай чрезвычайно маловероятным.
Сортировка с помощью прямого выбора
При сортировке этим методом выбирается наименьший элемент массива и меняется местами с первым. Затем выбирается наименьший среди оставшихся n – 1 элементов и меняется местами со вторым и т. д. до тех пор, пока не останется один самый больший элемент. Основной фрагмент программы может выглядеть так [11]:
for i:=l to n‑1 do
begin
k: =i;
x:=a[i];
for j:=i+1 to n do
if a[j]<x then begin k:=j; x:=a[k] end;a[k]:=a[i]; a[i]: =xend;
k– величина, хранящая индекс элемента, участвующего в операции обмена.
Сортировка файлов
Главная особенность методов сортировки последовательных файлов в том, что при их обработке в каждый момент непосредственно доступна одна компонента (на которую указывает указатель). Чаще процесс сортировки протекает не в оперативной памяти, как в случае с массивами, а с элементами на внешних носителях («винчестере», дискете и т. п.).
Понять особенности сортировки последовательных файлов на внешних носителях позволит следующий пример [9].
Предположим, что нам необходимо упорядочить содержимое файла с последовательным доступом по какому-либо ключу. Для простоты изучения и анализа сортировки условимся, что файл формируем мы сами, используя, как и в предыдущем разделе, некоторый массив данных. Его же будем использовать и для просмотра содержимого файла после сортировки. В предлагаемом ниже алгоритме необходимо сформировать вспомогательный файл, который позволит осуществить следующую процедуру сортировки. Сначала выбираем из исходного файла первый элемент в качестве ведущего, затем извлекаем второй и сравниваем с ведущим. Если он оказался меньше, чем ведущий, то помещаем его во вспомогательный файл, в противном случае во вспомогательный файл помещается ведущий элемент, а его замещает второй элемент исходного файла. Первый проход заканчивается, когда аналогичная процедура коснется всех последовательных элементов исходного файла. Ведущий элемент заносится во вспомогательный файл последним. Теперь необходимо поменять местами исходный и вспомогательный файлы. После nil проходов в исходном файле данные будут размещены в упорядоченном виде.
program sortirovka_faila_1;
{сортировка последовательного файла}
const n=8; type item= integer;
var a: array [1..n] of item;
i, k: integer; x, y: item;
fl, f2: text; {file of item};
begin
{заданиеискомогомассива}
for i:=1 to N do begin write ('введиэлемента ['i, '] = ');