Принцип Паскаля. Алгоритмы сортировки

Сел как-то Зигмунд за клавиатуру… Впрочем, хватит пространственных вступлений, тем более что речь в цикле статей, в отличие от Взгляда Разработчика, пойдёт о совершенно конкретных вещах. Ищем на антресолях запылённый Паскаль и в путь.

Сегодня мы поговорим об алгоритмах сортировки. Как вы знаете, каждый алгоритм применим для определённого типа задач из-за своей узкой специализации. Не всякий алгоритм подходит для данных, которые нужно сортировать на жёстком диске, не каждый справится с массивом вместимостью миллион ячеек, и не каждый с лёгкостью пройдёт частично упорядоченный массив небольшого размера. Но — перейдём от слов к делу.

Сортировка Пузырьком
Самый распространённый алгоритм сортировки с забавным названием «Метод пузырька»считается сугубо учебным, но при этом он самый простой для понимания, поэтому начнём именно с него.
Суть его проста: мы перебираем элементы массива, меняя местами пары чисел, стоящие не по порядку. К примеру, если в паре число «3» оказалось ниже «8», их надо поменять местами, заставляя «3» как бы «всплыть», приблизившись к началу массива. И этот пузырёк будет «всплывать» вверх до тех пор, пока не окажется на самом верху.
Обычно этот метод сортировки применяют к частично упорядоченным массивам небольших размеров любого типа.
Время выполнения такой сортировки находится в пределах от A*N до A*N^2, где A — время выполнения одного прохода цикла, N — количество ячеек массива.
Давайте посмотрим на пример кода такого алгоритма:

function bubblesort (X: list[1..n]);
var
 int i, j;
begin
 for i:=n downto 2 do
 for j:= 1 to i-1 do
 if (X[j] > X[j+1])
 // обмен элементов местами
 swap(X[j], X[j+1]);
end;

Итак, у нас есть массив размерностью N, по которому мы и идём, делая проверки. Заметьте, что промежуток поиска постепенно сужается. Последовательно делаются проверки в промежутках [1..(N-1)]; [1..(N-2)]; …; [1..2]. В каждом из них ищутся пары чисел, для которых выполнимо X[j]>X[j+1], т.е. число, стоящее раньше, больше числа, стоящего дальше него. Мы принимаем это неправильным и потому считаем своим долгом поставить каждого на своё место — swap(X[j],X[j+1]). Чтобы правильно поменять две переменные местами, чаще всего вводят третью, вспомогательную, куда заносят значение одной из двух. Однако, если вы сноб оптимизации, наверняка вы захотите справиться и без дополнительных перегрузок памяти и реализовать дополнительную функцию.
С этой целью можно использовать, к примеру, такой алгоритм обмена значений двух переменных (не самый оригинальный):

var
 A, B: integer;
begin
 A:=5; B:=4;
 A:=A+B;
 B:=A-B;
 A:=A-B;
end;

Нетрудно посчитать, что после выполнения этих действий переменные примут значения A=4 и B=5.
Приведу также код оптимизированной пузырьковой сортировки на Паскале:

P:=True; { флаг, показывающий, были ли при очередном проходе сделаны перестановки в массиве }
K:=1; {Количество просмотров}
while P do
begin
 P:= false
 For i := 1 To n-k Do
 If X[i] > X[i+1] Then
 Begin
 A := X[i];
 X[i]:=X[i+1];
 X[i+1]:=A;
 P:=true;
 End;
 k:=k+1;
end;

При входе в цикл сразу же говорим программе, что никаких перестановок не сделано. Так оно и будет, если не выполнится знакомое нам условие X[i] > X[i+1]. При такой оптимизации количество проходов по массиву сводится к минимуму, а значит снова сэкономлено драгоценное время! Друзья, а где же шампанское?

Шейкерная сортировка
Ещё один тип сортировки — это так называемая сортировка перемешиванием (она же — шейкерная сортировка). По сути, она является разновидность пузырьковой сортировки, вот только в то время, как минимальные значения плывут к одному концу массива, максимальные идут к его дну. Итог, разумеется, один — массив становится упорядоченным.
Этот метод может использоваться для сортировки больших массивов; в том числе — расположенных не в оперативной памяти, а на жёстком диске.
Время выполнения в данном случае заметно меньше и равно A*N/2.
Вот образец кода:

while e>s do
begin
 for i:=s to e-1 do
  if X[i]>X[i+1] then
   begin
    tmp:=X[i];
    X[i]:=X[i+1];
    X[i+1]:=tmp;
   end;
 for i:=e downto s+1 do
  if X[i]<x [i-1] then
   begin
    tmp:=X[i];
    X[i]:=X[i-1];
    X[i-1]:=tmp;
   end;
  s:= s+1;
  e:= e-1;
end;

Здесь S — первый элемент массива, а E — последний. В данном коде по умолчанию эти значения уже известны. Когда максимальный элемент встал в один конец, а минимальный в другой, то промежуток сортировки сужается на единицу с обоих концов массива — S:=S+1; E:=E-1.

Быстрая сортировка
Думаю, объяснять, откуда берёт название этот алгоритм, не требуется. Суть такова: разбиваем массив на две части и сортируем каждую из них при помощи рекурсии. По какому принципу делится массив? Выбираем элемент массива и относительно него все ячейки уходят в две группы — большие и меньшие этого элемента. Затем вызываем функцию сортировки для каждой из наших появившихся частей. Думаю, результат таких действий можно предугадать — все элементы массива найдут свои законные места.
Назначение: хаотично заполненные массивы (для частично упорядоченных массивов оптимальным методом будет пузырьковая сортировка). Не рекомендуется пробовать на достаточно длинных списках данных — выполнение цикла с рекурсией в таких случаях может привести к переполнению стёка, аварийному выходу программы и прочим нехорошим вещам.
Разбираемся с паскалевским кодом:

procedure QuickSort(var X: array of integer; min,max: Integer);
Var
 i, j, mid, tmp: integer;
Begin
 if min<max then
   begin
    mid:=X[min];
    i:=min-1;
    j:=max+1;
    while i<j do
     begin
      repeat i:=i+1;
      until X[i]>=mid;
      repeat j:=j-1;
      until X[j]< =mid;
      if i<j then
       begin
        tmp:=X[i];
        X[i]:=X[j];
        X[j]:=tmp;
       end;
     end;
    QuickSort(X, min, j);
    QuickSort(X, j+1, max);
  end;
end;

Здесь Mid — это так сказать элемент-граница раздела нашего массива на две части. Двумя циклами repeat определяем индексы элементов, находящихся «не в своей тарелке» и перебрасываем их на нужную сторону баррикад.

Сортировка методом Шелла
Ещё один метод сортировки — это сортировка методом Шелла. Суть алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно из кода, интервал между сравниваемыми элементами постепенно уменьшается до единицы. В итоге на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (разумеется, если такие перестановки являются необходимыми).

procedure SortShell(var X: array of real; N: Integer);
var
 h: Variant;
 c: Boolean;
 g, i, j: Integer;
 tmp: Real;
begin
 h:=1;
 g:=0;
 repeat h:=3*h+1
 until (h>=n);
 if (h>n) then
  begin
   h:=h/3;
   g:=h;
  end;
 n:=n-1;
 repeat i:=g;
 repeat j:=i-g;
 c:=True;
 repeat
  if X[j]< =X[j+g] then c:=False;
  else
   begin
    Tmp:=X[j];
    X[j]:=X[j+g];
    X[j+g]:=Tmp;
   end;
  j:=j-1
  until not((j>=0)and(C));
  i:=i+1
  until not(i< =n);
  h:=g;
  h:=h/3;
  g:=h;
  until not(g>0);
end;

Сортировка подсчётом
Особый метод, где собственно не используются привычные для нас операции сравнения элементов. Алгоритм работает невероятно быстро, если элементами массива являются целые числа, со значениями, которые занимают, относительно узкий диапазон. Пока выполняются эти условия, алгоритм работает отлично. Для примера можно привести результат сортировки 1 миллиона элементов со значением от 1-10000, на том же компьютере с процессором Pentium-133. Время быстрой сортировки было равно 3,93 секунды, результат же сортировки подсчётом был 0,37 секунды, то есть быстрее в 10 раз.

procedure CountingSort(var X: array of integer; min, max: integer);
var
 counter: array[0..100000] of integer;
 i, j, index: Integer;
begin
 // для всех элементов массива
 // указываем значение ноль
 for i:=0 to high(counter)
  do tmpX[i]:=0;
 for i:=min to max
  do counter[ar[i]]:=counter[ar[i]]+1;
 // устанавливаем значение
 // в правильную позицию
 index:=min;
 for i:=min to high(counter)-1 do
  begin
   for j:=0 to counter[i]-1 do
    begin
     ar[index]:=i;
     index:=index+1;
    end;
  end;
end;

Несмотря на лаконичность, этот код довольно сложен для понимания. TmpX здесь — это вспомогательный массив, который мы заполняем нулями. С помощью функции high узнаётся верхняя граница массива (в данном случае можно заменить на length). Далее мы подсчитываем, сколько раз в списке встречается очередной элемент, и к соответствующей записи счётчика прибавляем 1. Или иными словами, при исследовании элемента массива под номером i программа увеличивает значение counter[ar[i]]. И в конце, алгоритм проходит через весь массив счётчиков, помещая определённое число элементов в отсортированный массив. Для каждого значения i от 1 до N он добавляет counter[i] элементов со значением i.

Что лучше?
Итак, подытожим вышесказанное и выделим для каждого метода свои плюсы и минусы.
Пузырьковая сортировка:
+ быстро работает для почти отсортированных списков;
– медленно работает в остальных случаях.

Быстрая сортировка:
+ быстро сортирует большие списки;
– работает некорректно при большом количестве одинаковых значений.

Сортировка Шейкером:
+ сортирует данные на жёстком диске;
– работает медленнее, чем быстрая сортировка.

Метод Шелла:
+ сортирует дробные числа;
– требует много памяти для хранения временных значений.

Сортировка подсчётом:
+ очень быстро работает, если разброс входных значений не велик;
– медленно работает в случае если разброс составляет >log(N).

Но конечно, лучше всего сравнить алгоритмы наглядно. Лучше всего это можно сделать на этой странице.


Рекомендуем почитать: