Сортировка

Сортировка - это процесс перегруппировки заданного множества объектов в некотором определенном порядке. Рассмотрим некоторые методы сортировки  массивов.

Основное условие: выбранный метод должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте (в одном и том же массиве). Сначала разберем простые методы, их называют прямыми, где требуется порядка n² сравнений.

Методы сортировки "на том же месте" можно разбить на три основные категории:

- сортировки с помощью включения;

- сортировки с помощью выделения;

- сортировки с помощью обменов.

Все методы будем рассматривать на элементах массива 

a:array[1..n] of integer.

Сортировка с помощью прямого включения.

Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

В процессе поиска подходящего места для элемента х удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т.е. х сравнивается с очередным элементом a_j, а затем либо х вставляется на свободное место, либо a_j сдвигается вправо и процесс "уходит" влево.

Процесс просеивания может закончиться при выполнении одного из двух условий:

- найден элемент a_j с ключом, меньшим чем ключ у х;

- достигнут левый конец готовой последовательности.

Повторяющейся процесс с двумя условиями окончания позволяет воспользоваться приемом "барьера", поставив барьер a₀ со значением х.

  for i:=2 to 10 do

   begin

    x:=a[i];a[0]:=x;j:=i;

     while x<a[j-1] do

      begin

       a[j]:=a[j-1];j:=j-1;

      end;

    a[j]:=x;

   end;

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

For i:=2 to 10 do

  begin

    c:=a[i]; l:=1;r:=i;

    while l<r do

       begin

          m:=(l+r) div 2;

          if a[m]<=c then l:=m+1 else r:=m;

       end;

    for j:=i downto r+1 do

      a[j]:=a[j-1];

    a[r]:=c;

  end;