В повседневной жизни нам очень часто приходится раскладывать наши вещи, книги, кассеты диски и т. п. в удобном для нас порядке. Для чего? Чтобы облегчить их дальнейший поиск. В библиотеке мы раскладываем книги по авторам, в телефонной книге мы записываем фамилии по алфавиту, в словаре слова расставлены по алфавиту. С появлением компьютеров люди стали использовать «железных монстров» для хранения больших объемов информации. Очевидно, что появилась потребность обработки данных. Две самые необходимые для этого функции — это сортировка и поиск. На первой мы и остановимся.

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

Обычно алгоритмы сортировки разделяются на два типа — сортировка массивов и сортировка последовательностей. В этой статье речь пойдет о сортировке массивов как наиболее часто встречающейся задаче при создании программы обработки данных. Под «массивом» я подразумеваю одномерный массив. Думаю, для вас не составит труда после прочтения статьи написать алгоритм сортировки двухмерного или более массива. Моя цель — не написать вам готовую программу, а познакомить с идеей, методом. Для практичности за описанием алгоритма будет следовать исходный код программы-примера на языке Паскаль. Почему на Паскале? Да потому что это наиболее распространенный язык для учебных целей. И, на мой взгляд, Паскаль лучше всего подходит для демонстрации механизмов сортировки.

Для оценки эффективности алгоритма мы будем использовать два значения: количество сравнений ключей (K) и число пересылок элементов (S). Последнее значение представляет для нас большой интерес — пересылка данных в памяти является более длительным процессом, чем сравнение. Также при описании алгоритмов я буду использовать такие величины: n — количество элементов массива, А[1..n] — сортируемый массив, x — переменная того же типа, что и элементы массива. Будем считать, что у нас массив целых чисел (А: array[l..n] of integer; х: integer;).

По количеству необходимых сравнений алгоритмы сортировки разделяют на два класса: более простые требуют примерно n^2 сравнений, а наиболее эффективные — порядка n*log(n). Я начну с более простых и наглядных алгоритмов. Первый метод сортировки, о котором я хочу рассказать, называется «сортировка с помощью прямого включения». Идея такова: мы по порядку берем элементы массива и ставим на их «законное» место. Начиная со второго, мы перебираем все элементы массива и последовательно сравниваем с элементами, которые имеют индекс меньше данного. Если наш элемент меньше предыдущего, то меняем их местами и продолжаем сравнивать дальше, если больше, то оставляем его — он уже на своем месте. И так продолжаем до тех пор, пока не достигнем левой границы массива. Чтобы в данном случае процесс сравнивания не уходил за пределы левой границы массива, необходимо создать так называемый «барьер» — добавить в начало массива ячейку (например, А[0]), в которую будем заносить сортируемый в этом проходе элемент. Вот полный код алгоритма:

Procedure Insertion;
var
  k, m, x: integer;
  A: array[0..n] of integer;
begin
  for k:=2 to n do
  begin
    x:=A[k];
    A[0]:=x;
    m:=k;
    while x<A[m-1] do
    begin
      A[m]:=A[m-l];
      m:=m-l;
    end;
    A[m]:=x
  end
end;

Здесь A[0] — вышеупомянутый барьер, A[1..n] — сортируемый массив.

Мой совет: для простейших алгоритмов сортировок попробуйте написать на бумажке какую-нибудь последовательность из 4-5 чисел. А потом «прогоните» ее на листочке через алгоритм сортировки. При этом пишите значения всех переменных и изменения массива на каждом шаге. Это не так уж трудно сделать для первых трех алгоритмов и займет не больше половины тетрадного листа. Таким образом гораздо легче понять алгоритм. Конечно, для усовершенствованных методов это представляет значительную сложность, но и в этом случае есть выход. Например, в Delphi можно запустить программу в пошаговом режиме и смотреть значения всех переменных программы — очень полезная вещь для того чтобы понять, как работает какая-то часть программы. Не пренебрегайте этим советом!

Средние числа сравнения ключей и пересылки элементов имеют следующие значения: K=(n^2+n-2)/4, S=(n^2+9n-10)/4 Минимальные и максимальные значения такие: Kmin=n-1, Smin=3*(n-1), Kmax=(n^2+n-4)/4, Smax=(n^2+3n-4)/2. У алгоритма есть один существенный недостаток. Предположим, у нас есть массив чисел: 3,7,4,6,8,2. В этом случае последний элемент массива (2) придется «тащить» через весь массив.

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

Procedure Selection;
var
  k, m, t, x: integer;
  A: array[l..n] of integer;
begin
  for k:=1 to n-1 do
  begin
    m:=k; x:=A[k];
    for t:=k+l to n do
      if A[t]<x then
      begin
        m:=t;
        x:=A[m];
      end;
    A[m]:=A[k];
    A[k]:=x
  end
end;

В данном случае никакого барьера (A[0]) не нужно, и мы рассматриваем массив в диапазоне [1..n].

Сравнение ключей: K=(n^2-n)/2. Для пересылки ключей вычислить среднее значение нелегко, потому привожу минимальное (ключи уже отсортированы) и максимальное (ключи стоят в обратном порядке) значения: Smin=3*(n-1), Smax=n^2/4+3*(n-l). Как видим, алгоритм прямого выбора в большинстве случаев эффективнее прямого включения. Исключение составляет лишь ситуация, когда массив уже упорядочен или почти упорядочен. Однако в этом случае выигрыш не столь велик, и в целом данный метод предпочтительнее, чем предыдущий.

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

При таких проходах по массиву мы сдвигаем наименьший элемент к левому краю. Если мы представим массив как вертикальную цепочку, то элементы при сортировке будут как пузырьки «всплывать» на свой уровень. Поэтому более широко известное наименование данного метода — «пузырьковая сортировка». Вот как выглядит код этого алгоритма:

Procedure BubbleSort;
var
  k, m, x: integer;
  A: array[l..n] of integer;
  f: boolean;
Begin
  repeat
    f:=false;
    for k:=1 to n-1 do
      if A[k]>A[k+1] then
      begin
        x:=A[k];
        A[k]:=A[k+l];
        A[k+l]:=x;
        f:=true;
      end;
  until f=false;
end;

Здесь используется переменная f в качестве флага. Если f=true, значит, в последнем проходе были сделаны перестановки и нужны еще проходы, а если f=false, значит, перестановок в последнем проходе не было и массив уже отсортирован. В этом алгоритме есть также свой недостаток: если наименьшее число расположено в конце массива, то для того, чтобы переместить его в начало (на его «законное» место), потребуется n-1 проходов. А в это время наибольший элемент с начала массива переместится в конец за один проход. Согласитесь, довольно неприятный факт. Вывод напрашивается сам собой: необходимо проходить массив с разных сторон по очереди, т. е. первый раз с начала в конец, второй — с конца в начало, третий — опять с начала в конец и т. д. Такой улучшенный алгоритм называется «шейкерной сортировкой» (ShakerSort). А вот программу для данного варианта предлагаю написать самим. Если вы полностью разобрались с методом пузырьковой сортировки, то это не будет для вас сложной задачей.

Для пузырьковой и шейкерной сортировок подсчитать число сравнений ключей и пересылок довольно сложно. Поэтому объективно сравнить эффективность последних двух методов с предыдущими мы сможем в конце статьи — я приведу время сортировки массива различными алгоритмами.

Теперь мы вплотную подошли к обсуждению улучшенных методов сортировки. Разобраться в них гораздо сложнее. В 1959 году Д. Шелл предложил усовершенствованную сортировку прямого включения. Идея довольно простая. Сначала мы сортируем элементы, отстоящие друг от друга на расстоянии 4. Например, берем элемент A[1] и сравниваем его с элементом A[5] (A[1+4]), если А[1] больше А[5], то меняем их местами. Потом берем A[2] и сравниваем с A[6] и т. д. После этого прохода с «четвертной» сортировкой проходим по массиву опять, но уже сортируем элементы, отстоящие друг от друга на расстоянии 2. И на последнем проходе идет обычная одинарная сортировка. Последовательность расстояний можно менять, как и их количество. Поэтому для обобщения все t расстояний занесем в массив s[1..t]. Сортировка каждого расстояния делается как сортировка прямым включением. Для условия окончания сортировки придется установить барьер, и не один.

procedure ShellSort(var A: mas);
const
  steps = 12;
var
  i, j, l, k, p, n : Integer;
  x : itp;
  s : array [1..steps] of Integer;
begin
  k := 1;
  { Формируем последовательность чисел -
  шаги, с которыми выбираем сортируемые подмассивы }
  for i := steps downto 1 do
  begin
    s[i] := k;
    k := k * 2 + 1;
  end;
 
  { Сортировки подмассивов вплоть до шага 1 -
  обычной сортировки пузырьком }
  for k := 1 to steps do
  begin
    l := s[k];
    { Для каждого шага l нужно отсортировать l подмассивов }
    for p := 1 to l do
    begin
      i := max - l;
      n := 1;
      { Сортировка подмассива пузырьком с остановкой }
      { Подмассив - это (A[p], A[p+l], A[p+2*l], ...) }
      while n > 0 do
      begin
        n := 0;
        j := p;
        while j <= i do
        begin
          if A[j] > A[j + l] then
          begin
            x := A[j];
            A[j] := A[j + l];
            A[j + l] := x;
            n := 1;
          end;
          j := j + l;
        end;
        i := i - l;
      end;
    end;
  end;
end;

Последний алгоритм, который мы рассмо¬трим, является самым быстрым из всех ныне существующих. Автор Ч. Хоар так и назвал его — Quicksort. В Quicksort сначала делают перемещения на большие расстояния. Для этого наугад выбираем в массиве элемент х. Просматриваем массив слева, пока не встретим элемент A[i]>x, потом смотрим массив справа, пока не обнаружим элемент А[j]<х. Меняем местами оба найденных элемента и продолжаем просмотр в том же ключе, пока просмотры слева и справа не встретятся на середине. После такой операции массив будет разбит на две половины: левую — с ключами меньше или равными х, и правую — с ключами большими или равными х. В таких проходах х также играет роль барьера; описание же массива таково: A: array[l..n] of integer;

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

Procedure Quicksort;

  procedure sort(L,R: integer);
  var
    i, j, w, x: integer;
  begin
    i:=L; j:=R; x:=a[(L+R) div 2];
    repeat
      while A[i]<x do i:=i+l;
      while x<A[j] do j:=j-l;
      if i<j then
      begin
        w:=A[i];
        A[i]:=A[j];
        A[j]:=w;
        i:=i+l; j:=j-l;
      end;
    until i>j;
    if L<j then sort(L,j);
    if i<R then sort(i,R);
  end;
 
begin
  sort(l, n)
end;

В основной процедуре QuickSort вызываем подпроцедуру сортировки элементов от 1 до n. В подпроцедуре sort мы берем за х середину данного диапазона и разделяем диапазон вышеуказанным методом. Потом вызываем эту подпроцедуру опять, но для половинок и т. д. Кстати, х и w должны быть того же типа, что и элементы массива.

В данном случае среднее значение S=(n-1/n)/6.

Теперь осталось обобщить все результаты и сделать выводы (см. табл). Для объективной оценки эффективности всех алгоритмов приведу время сортировки одного и того же массива (элементы расставлены наугад) различными методами. Из таблицы мы видим, что пузырьковая сортировка и ее улучшенный вариант (шейкерная) гораздо хуже всех остальных. Внимания заслуживают лишь улучшенные методы. Хотя метод Шелла показал очень хороший результат, лучшим все же является QuickSort. Кстати, если массив уже упорядочен, то все эффективные методы показывают результат похуже, чем обычные.

Ну вот и все! Пробуйте, экспериментируйте с различными алгоритмами