Пусть дан массив A из N чисел. Требуется отсортировать его в порядке возрастания, т. е. изменить порядок чисел в A так, что при 1<=i<N A[i] будет не больше, чем A[i+1]. В данном разделе мы рассмотрим несколько алгоритмов сортировки.
Данная сортировка будет просто помещать по очереди каждый элемент на его место, сдвигая остальные элементы массива:
const MaxN = 10000; var N : Integer; A : array [1 .. MaxN] of Longint; procedure Swap(X,Y : Integer); var T : Longint; begin T := A[X]; A[X] := A[Y]; A[Y] := T; end; procedure Bubble_Sort; var I,J : Integer; begin for I:=1 to N do for J:=1 to I-1 do if A[I]<A[J] then Swap(I,J); end; |
Несложно понять, что сортировка пузырьком требует O(N^2) времени и O(1) дополнительной памяти.
Для данной сортировки мы используем структуру, называемую кучей. Куча - массив чисел (обозначим его за H), в котором для i-го элемента выполняется основное свойство кучи: H[i]>=H[2i] и H[i]>=H[2i+1], если индексы 2i и 2i+1 не выходят за границу массива.
Алгоритм состоит из двух частей: построения кучи и собственно сортировки.
Нам потребуется процедура восстановления кучи (Heapify
).
Она используется в том случае, когда основное свойство кучи может быть нарушено
для некоторого элемента с индексом X. Из элементов с индексами X,
2X,2X+1 выбирается наибольший Y; если X<>Y, то процедура восстановления
кучи рекурсивно вызывается для элемента Y, так как основное свойство кучи
могло быть для него нарушено.
Куча строится из массива A с помощью вызова процедуры восстановления кучи последовательно для всех элементов, начиная с конца.
Процесс сортировки состоит из N-1 шагов. На каждом из них наибольший элемент кучи - A[1] - помещается в ее конец, а элемент с конца кучи ставится в начало, после чего куча укорачивается на один элемент и вызывается процедура восстановления для первого элемента. Ясно, что после конца работы алгоритма массив A будет отсортирован в порядке возрастания.
Реализация алгоритма:
const MaxN = 10000; var N,M : Integer; A : array [1 .. MaxN] of Longint; procedure Swap(X,Y : Integer); var T : Longint; begin T := A[X]; A[X] := A[Y]; A[Y] := T; end; procedure Heapify(X:Integer); var Y : integer; begin Y := X; if (2*X<=M) and (A[2*X]>A[Y]) then Y := 2*X; if (2*X+1<=M) and (A[2*X+1]>A[Y]) then Y := 2*X+1; if X<>Y then begin Swap(X,Y); Heapify(Y); end; end; procedure Build_Heap; var I : integer; begin for I:=N downto 1 do Heapify(I); end; procedure Heap_Sort; begin M := N; Build_Heap; while M>1 do begin Swap(1,M); Dec(M); Heapify(1); end; end; |
Алгоритм сортировки кучей требует O(Nlog(N)) времени
(O(N) для построения кучи и O(log(N)) для каждого
из вызовов Heapify
в собственно сортировке)
и O(1) дополнительной памяти (при совмещении кучи с
исходным массивом).
Быстрая сортировка основана на принципе "разделяй и властвуй". Пусть нам нужно отсортировать в массиве A элементы c l-го по r-тый. Мы сначала поменяем порядок элементов в нем так, что для некоторого числа m от l до r-1 для всех i от l до q и j от q+1 до r будет выполнено условие A[i]<=A[j] (процедура разделения массива), а затем вызовем процедуру сортировки для частей массива от l до q и от q+1 до r, пока не придем к частям массива единичной длины.
В описанном здесь алгоритме мы будем делить массив следующим образом.
В левую часть массива (от l до q) поместим элементы, не большие
A[l], а в правую (от q+1 до r) - не меньшие A[l]. Разделение массива
реализовано процедурой Partition
.
Реализация алгоритма:
const MaxN = 10000; var N : Integer; A : array [1 .. MaxN] of Longint; procedure Swap(X,Y : Integer); var T : Longint; begin T := A[X]; A[X] := A[Y]; A[Y] := T; end; function Partition(L,R : Integer) : Integer; var X,Y : Integer; begin X := L-1; Y := R+1; repeat repeat Dec(Y); until A[Y]<=A[L]; repeat Inc(X); until A[X]>=A[L]; if X |
Быстрая сортировка в худшем случае требует O(N^2) времени, а в среднем (по всем перестановкам элементов в массиве) - O(Nlog(N)) времени и O(log(N)) памяти.
Сортировка слиянием, как и быстрая сортировка, основана на принципе
"разделяй и властвуй". Отрезок массива от l до r разбивается
на две половины, сортируется каждая из них, а затем вызывается
процедура слияния (Merge
), которая из двух последовательных
отсортированных частей массива создает одну.
Процедура слияния устроена просто: мы запоминаем исходный массив, а затем по очереди выбираем из первой или второй половины минимальный элемент и добавляем его в новый массив.
Реализация алгоритма:
const MaxN = 5000; var N : Integer; A,T : array [1 .. MaxN] of Longint; procedure Merge(L,M,R : Integer); var I : Integer; CLeft,CRight : Integer; begin for I:=L to R do T[I] := A[I]; CLeft := L-1; CRight := M; while (CLeft<M) or (CRight<R) do begin if (CRight>=R) or ((CLeft<M) and (T[CLeft+1]<T[CRight+1])) then begin Inc(CLeft); A[CLeft+CRight-M] := T[CLeft]; end else begin Inc(CRight); A[CLeft+CRight-M] := T[CRight]; end; end; end; procedure Merge_Sort_Call(L,R : integer); var M : Integer; begin if R>L then begin M := (L+R) div 2; Merge_Sort_Call(L,M); Merge_Sort_Call(M+1,R); Merge(L,M,R); end; end; procedure Merge_Sort; begin Merge_Sort_Call(1,N); end; |
Алгоритм сортировки слиянием требует O(Nlog(N)) времени и O(N) дополнительной памяти (для хранения массива T)).
© Semyon Dyatlov, 2002 | Пишите мне |