Методы сортировки

Конечно, этого недостаточно: процесс возобновляется с новым  значением h, меньшим предыдущего. И  так до тех пор, пока не будет достигнуто значение h=1.

В настоящее время неизвестна последовательность h_i, h_i-1, h_i-2, ..., h₁, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1=3h_i+1, а h₁=1. Начинается процесс с h_m-2, где m - наименьшее целое такое, что h_m³ n. Другими словами h_m-2 первый такой член последовательности, что h_m-2³ [n/9].

Теперь запишем алгоритм:

Step := 1;

while Step < N div 9 do Step := Step*3 + 1;

Repeat

  for k := 1 to Step do

  begin

  i := Step + k;

    while i <= N do

    begin

      x := A^[i];

      j := i - Step;

      while (j >= 1) and (A^[j]>x) do

      begin

        A^[j + Step] := A^[j];

        Dec(j);

      end;

      A^[j + Step] := x;

      Inc(i, Step);

    end;

  end;

  Step := Step div 3;

until Step=0;

Как показывают теоретические  выкладки, которые мы приводить не будем, сортировке методом Шелла  требуется в среднем 1,66n^1,25 перемещений.

2.2.4. Сортировка  извлечением

В этих методах массив также  делится на уже отсортированную  часть A[i+1], A[i+1], ..., A[n] и еще не отсортированную A[1], A[2], ..., A[i]. Но здесь из неотсортированной  части на каждом шаге мы извлекаем  максимальный элемент. Этот элемент  будет минимальным элементом  отсортированной части, так как  все большие его элементы мы извлечем на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части.

2.2.4.1. Простое извлечение

При простом извлечении мы будем искать максимальный элемент  неотсортированной части, просматривая ее заново на каждом шаге. Найдя положение  максимального элемента поменяем его  с A[i] местами.

for i := N downto 2 do

begin

  MaxIndex := 1;

  for j := 2 to i do

    if A[j]>A[MaxIndex] then

      MaxIndex := j;

  Tmp := A[i]; A[i] := A[MaxIndex];

  A[MaxIndex] := Tmp;

end;

Простое извлечение во всех случаях имеет временную сложность T(n²) (два вложенных цикла, зависящих от n линейно).

2.2.4.2. Древесная  сортировка

Древесная сортировка избегает необходимости каждый раз находить максимальный элемент. При следовании этому методу постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться  в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом.

Двоичное дерево имеет  элемент, называемый корнем. Корень, как и любой другой элемент дерева (называемый вершиной), может иметь до двух элементов-сыновей. Все элементы, кроме корневого имеют элемент-родитель.

Условимся нумеровать вершины  числами 1, 2, ...: сыновьями вершины  с номером k будут вершины с  номерами 2*k и 2*k+1, - как это сделано  на рисунке. Как можно заметить, двоичное разложение номера вершины указывает  путь к этой вершине от корня (0 - к  левому сыну, 1 - к правому сыну). Например, 9₁₀=1001₂. Первую 1 двоичного разложения пропускаем (в начале всегда стоит 1). Затем идет 0, то есть от корня переходим к левому сыну (вершина номер 2₁₀=10₂), потом снова 0 - переходим к левому сыну (вершина номер 4₁₀=100₂), последней следует цифра 1 - переходим к правому сыну и как раз попадаем в вершину номер 9₁₀=1001₂. Значит номер элемента однозначно определяет его положение в дереве.

Введенный способ нумерации  вершин дерева позволяет хранить  деревья в массиве, где индекс массива будет номером вершины.

Пусть A[1]..A[n] - массив, подлежащий сортировке. Вершинами дерева будут  числа от 1 до n; о числе A[i] мы будем  говорить как о числе, стоящем  в вершине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем  хранить в переменной k. Таким  образом, в процессе работы алгоритма  массив A[1]..A[n] делится на две части: в A[1]..A[k] хранятся числа на дереве, а  в A[k+1] .. A[n] хранится уже отсортированная  в порядке возрастания часть  массива - элементы, уже занявшие свое законное место.

На каждом шаге алгоритм будет изымать максимальный элемент  дерева и помещать его в отсортированную  часть, на освободившееся в результате сокращения дерева место.

Договоримся о терминологии. Вершинами дерева считаются числа  от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2*s и 2*s+1. Если оба этих числа больше k, то сыновей нет; такая вершина  называется листом. Если 2*s=k, то вершина s имеет ровно одного сына (2*s).

Для каждого s из 1..k рассмотрим "поддерево" с корнем в s: оно  содержит вершину s и всех ее потомков (сыновей, сыновей сыновей и т.д. - до тех пор, пока мы не выйдем из отрезка 1..k).

Вершину s будем называть регулярной, если стоящее в ней число - максимальный элемент s-поддерева; s-поддерево назовем регулярным, если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.)

Схема алгоритма такова:

k:= n

... Сделать 1-поддерево регулярным;

while k<>1 do

begin

  ... обменять местами A[1] и A[k];

  k := k - 1;

  {A[1]..A[k-1] <= A[k] <=...<= A[n];

   1-поддерево регулярно везде,  кроме, возможно,

   самого корня }

  ... восстановить регулярность 1-поддерева всюду

end;

В качестве вспомогательной  процедуры нам понадобится процедура  восстановления регулярности s-поддерева  в корне. Вот она:

{s-поддерево регулярно везде,  кроме, возможно, корня}

t := s;

{s-поддерево регулярно везде,  кроме, возможно,

 вершины t}

while ((2*t+1<=k) and (A[2*t+1]>A[t])) or

  ((2*t<=k) and (A[2*t]>A[t])) do

begin

  if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then

  begin

    ... обменять A[t] и A[2*t+1];

    t := 2*t + 1;

  end else

  begin

    ... обменять A[t] и A[2*t];

    t := 2*t;

  end;

end;

Чтобы убедиться в правильности этой процедуры, посмотрим на нее  повнимательнее. Пусть в s-поддереве  все вершины, кроме разве что  вершины t, регулярны. Рассмотрим сыновей  вершины t. Они регулярны, и потому содержат наибольшие числа в своих  поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве  могут претендовать число в самой  вершине t и числа, содержащиеся в  ее сыновьях. (В первом случае вершина t регулярна, и все в порядке.) В  этих терминах цикл можно записать так:

while наибольшее число не в  t, а в одном из сыновей do

begin

  if оно в правом сыне then

  begin

    ...поменять t с ее правым  сыном; t:= правый сын

  end else

  begin {наибольшее число - в  левом сыне}

    ...поменять t с ее левым  сыном; t:= левый сын

  end

end

После обмена вершина t становится регулярной (в нее попадает максимальное число t-поддерева). Не принявший участия  в обмене сын остается регулярным, а принявший участие может  и не быть регулярным. В остальных  вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева переставились), так что регулярность не нарушилась.

Эта же процедура может  использоваться для того, чтобы сделать 1-поддерево регулярным на начальной  стадии сортировки:

k := n;

u := n;

{все s-поддеревья с s>u регулярны  }

while u<>0 do

begin

  {u-поддерево регулярно везде,  кроме разве что корня}

  ... восстановить регулярность u-поддерева в корне;

  u:=u-1;

end;

Теперь запишем процедуру  сортировки на паскале:

procedure Sort;

Var u, k: Integer;

procedure Exchange(i, j: Integer);

Var Tmp: Integer;

begin

  Tmp := x[i]; A[i] := A[j]; A[j] := Tmp;

end;

procedure Restore(s: Integer);

Var t: Integer;

begin

  t:=s;

  while ((2*t+1<=k) and (A[2*t+1]>A[t])) or

   ((2*t<=k) and (A[2*t]>A[t])) do

  begin

    if (2*t+1<=k) and (A[2*t+1]>=A[2*t]) then

    begin

      Exchange(t, 2*t+1);

      t := 2*t+1;

    end else

    begin

      Exchange(t, 2*t);

      t := 2*t;

    end;

  end;

end;

begin

  k:=n;

  u:=n;

  while u<>0 do

  begin

    Restore(u);

    Dec(u);

  end;

  while k<>1 do

  begin

    Exchange(1, k);

    Dec(k);

    Restore(1);

  end;

end;

Преимущество этого метода перед другими в том, что он, имея T_max(n*log(n)) (внутри внешнего цикла зависящего от n линейно вызывается процедура Restore, требующая порядка log(n) действий), при сортировке не требует дополнительной памяти порядка n.

2.2.5. Сортировка  обменами

Как следует из названия метода он сортирует массив путем  последовательных обменов пар элементов  местами.

2.2.5.1. Пузырьковая  сортировка

Пузырьковая сортировка - один из наиболее широко известных алгоритмов сортировки. В этом методе массив также  делится на две части: отсортированную  и неотсортированную. На каждом шаге метода мы пробегаем от меньших индексов к большим по неотсортированной  части, каждый раз сравнивая два  соседних элемента: если они не упорядочены  между собой (меньший следует  за большим), то меняем их местами. Тем  самым за один проход путем последовательных обменов наибольший элемент неотсортированной  части сдвинется к ее концу.

Алгоритм называют пузырьковой  сортировкой, потому что на каждом шаге наибольший элемент неотсортированной  части подобно пузырьку газа в  воде всплывает вверх.

Запишем алгоритм на языке  Паскаль, заметив, что в том случае, когда за очередной проход не было сделано ни одного обмена, массив уже  отсортирован и следующие проходы  можно пропустить. Для отслеживания такой ситуации введем логическую переменную Flag - признак совершения обмена на очередном  проходе:

for i := N-1 downto 1 do

begin

  Flag := false;

  for j := 1 to i do

    if a[j]>a[j+1] then

    begin

      Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

      Flag := true;

    end;

  if not Flag then Break;

end;

Этот алгоритм имеет среднюю  и максимальную временные сложности T(n²) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к T(n).

2.2.5.2. Быстрая сортировка (Хоара)

Эту сортировку называют быстрой, потому что на практике она оказывается  самым быстрым методом сортировки из тех, что оперируют сравнениями.

Этот метод является ярким  примером реализации принципа «разделяй  и властвуй». Как показывают теоретические  выкладки наиболее эффективным в  общем случае оказывается разделение задачи на две равные по сложности  части, что мы и будем пытаться делать в этом методе.

На каждом шаге метода мы сначала выбираем «средний» элемент, затем переставляем элементы массива  так, что он делится на три части: сначала следуют элементы, меньшие  «среднего», потом равные ему, а в  третьей части - большие. После такого деления массива остается только отсортировать первую и третью его части, с которыми мы поступим аналогично (разделим на три части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован.

Запишем то, что мы сейчас сформулировали:

procedure Sort;

procedure QuickSort(a, b: Longint);

Var

  x: Longint; {индекс «среднего» элемента}

begin

  x := элемент_выбранный_средним;

  ...деление на три части:

     1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b]

  if i>a then QuickSort(a, i);

  if b>j then QuickSort(j, b);

end;

begin

  Sort(1, N);

end;

Выбор «среднего» - задача непростая, так как требуется, не производя  сортировку, найти элемент со значением  максимально близким к среднему. Здесь, конечно, можно просто выбрать  произвольный элемент (обычно выбирают элемент, стоящий в середине сортируемого подмассива), но пойдем чуть дальше: из трех элементов (самого левого, самого правого и стоящего посередине) выберем  средний:

i := A[l]; y := A[(l+r)div 2]; j := A[r];

if i<=y then

  if y<=j then

    x := (l+r)div 2

  else

    if i<=j then

      x := r

    else

      x := l

else

  if y>=j then

    x := (l+r)div 2

  else

    if i>=j then

      x := r

    else

      x := l;

Теперь нам надо разделить  массив относительно элемента A[x] так, чтобы сначала следовали элементы, меньшие A[x], затем сам элемент A[x], а потом уже элементы, большие  или равные A[x]. Для этого мы, двигаясь слева найдем первый элемент A[i], больший A[x], и, двигаясь справа, - первый элемент A[j], меньший A[x]. Если i окажется меньше j, то это значит, что массив еще  не поделен на три искомых части, в таком случае обменяем местами  элементы A[i] и A[j], а затем продолжим  поиск слева от A[i] и справа от A[j].

i := l; j := r; x := A[x];

repeat

  while A[i] < x do Inc(I);

  while x < A[j] do Dec(j);

  if i <= j then

  begin

    y := A[i]; A[i] := A[j]; A[j] := y;

    Inc(i); Dec(j);

  end;

until i > j;

Пойдем дальше. Заметим, что  все-таки наш способ нахождения «среднего» элемента подмассива в худшем случае приведет к тому, что после деления, например, правая и средняя части  поделенного массива будут содержать  по одному элементу, а левая все  остальные. В этом случае, если мы сначала  вызовем QuickSort для левой части, то (опять же в худшем случае) это  может породить порядка N рекурсивных  вызовов. А значит нам надо будет  завести дополнительную память размером пропорциональным N и пространственная сложность будет O(N). Этого можно  избежать, если сначала вызывать QuickSort для меньшей части. Тогда можно  гарантировать пространственную сложность O(log(N)).

Теперь осталось только собрать  вместе части программы:

procedure Sort;

procedure QuickSort(a, b: Longint);

Var

  x: Longint; {индекс «среднего» элемента}

begin

  i := A[l]; y := A[(l+r)div 2]; j := A[r];

  if i<=y then

    if y<=j then

      x := (l+r)div 2

    else

      if i<=j then

        x := r

      else

        x := l

  else

    if y>=j then

      x := (l+r)div 2

    else

      if i>=j then

        x := r

      else

        x := l;

  i := l; j := r; x := A[x];

  repeat

    while A[i] < x do Inc(i);

    while x < A[j] do Dec(j);

    if i <= j then

    begin

      y := A[i]; A[i] := A[j]; A[j] := y;

      Inc(i); Dec(j);

    end;

  until i > j;

  if l-j<i-r then

  begin

    if l < j then QuickSort(l, j);

    if i < r then QuickSort(i, r);

  end else

  begin

    if i < r then Sort(i, r);

    if l < j then Sort(l, j);

  end;

end;

begin

  QuickSort(1, N);

end;

В худшем случае этот алгоритм дает временную сложность T_max(N²) (для случая, когда все выборки «среднего» элемента оказались неудачны), но как показывают теоретические исследования вероятность такого случая очень мала. В среднем же и в лучшем случае получим T(N*log(N)).

2.2.6. Сортировка  слиянием

Этот метод сортирует  массив последовательным слиянием пар  уже отсортированных подмассивов, поэтому его и назвали сортировкой  слиянием.

Пусть k - положительное целое  число. Разобьем массив A[1]..A[n] на отрезки  длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и  т.д.) Последний отрезок будет  неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.