birmaga.ru
добавить свой файл

1
Сортировка

Сортировки


Пусть дан массив A из N чисел. Требуется отсортировать его в порядке возрастания, т. е. изменить порядок чисел в A так, что при 1<=i

Сортировка пузырьком


Данная сортировка будет просто помещать по очереди каждый элемент на его место, сдвигая остальные элементы массива:

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]
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
Swap(X,Y)

until X>=Y;

Partition := Y;

end;
procedure Quick_Sort_Call(L,R : Integer);

var

M : Integer;

begin

if R>L then

begin

M := Partition(L,R);

Quick_Sort_Call(L,M);

Quick_Sort_Call(M+1,R);

end;

end;
procedure Quick_Sort;

begin

Quick_Sort_Call(1,N);

end;


Быстрая сортировка в худшем случае требует 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
begin

if (CRight>=R) or ((CLeft
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)).