Сортировки

Пусть дан массив 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=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<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 Пишите мне