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

Сортировка "пузырьком"

Если в воде находиться пузырёк с воздухом, то он постепенно поднимается наверх. Связано это явление с силой Архимеда: плотность воздуха меньше плотности воды. Сортировка "пузырьком" немного напоминает описанный процесс.

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

  const N=10; {Количество элементов массива}

 var a: array[1..N] of integer; {массив}

 i: integer; {счётчик для цикла}

 f: boolean; {Признак наличия неупорядоченных пар}

 c: integer; {Переменная для промежуточного хранения}

 .......

repeat

 f:=false; {Пока неупорядоченных пар не было}

 for i:=1 to N-1 do  {Просматриваем все пары рядом стоящих элементов}

 begin

   if a[i]>a[i+1] then {Если пара стоит в неправильном порядке}

   begin

     f:=true; {Есть неупорядоченная пара}

     c:=a[i];a[i]:=a[i+1];a[i+1]:=c; {Меняем местами элементы массива}

   end;

 end;

until not f; {Ждём, пока не исчезнут все неупорядоченные пары}

Метод сортировки "пузырьком" является одним из самых простых и, одновремнно, самых медленных методов.

Метод простого выбора

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

  const N=10; {Количество элементов массива}

  var a: array[1..N] of integer; {массив}

  i,j: integer; {счётчики для цикла}

  c:   integer; {Переменная для промежуточного хранения}

  c2:  integer; {Переменная для промежуточного хранения}

  .......

for i:=1 to N-1 do begin 

  {цикл по первому обрабатываемому элементу массива}

  c2:=i; {индекс предполагаемого минимального элемента}

  for j:=i+1 to N do 

    {поиск минимального элемента}

    if a[c2]>a[j] then c2:=j; {если в c2 индекс не минимального элемента, 

       то в c2 записывается индекс меньшего элемента}

    c:=a[i];a[i]:=a[c2];a[c2]:=c; {Меняем местами элемент массива}

end;

Метод Шелла

Недостаток метода сортировки "пузырьком" - работа с рядом стоящими элементами. В результате, элементы, которым надо "добраться" с одного конца массива до другого, делают это крайне долго. Метод Шелла аналогичен методу сортировки "пузырьком", однако работает с далеко отстоящими друг от друга элементами массива. На этот раз приведу сразу текст программы:

  const N=10; {Количество элементов массива}

  var a:       array[1..N] of integer; {массив}

      p:       boolean; {флаг наличия перестановки}

      l,d,i,j: integer; {служебные переменные}

  ...........

d:=N div 2; {Расстояние между обрабатываемыми элементами массива,

      на каждом этапе алгоритма уменьшается в 2 раза вплоть до 0,

      когда происходит останов алгоритма}

while d>0 do

begin

  for j:=1 to N-d do {Перебор всех пар элементов массива,

      расстояние между которыми равно d}

  begin

    l:=j  {запоминаем индекс текущего элемента}

    repeat

      p:=false;  {пока элементы не переставлялись}

      if a[l]then begin {если порядок нарушен, то}

        c:=a[l];a[l]:=a[l+d];a[l+d]:=c; {меняем местами элементы массива}

        l:=l-d;    {перейдём к той паре, в которую

    входит меньший из переставленных элементов}

        p:=true;   {запомним, что была перестановка}

      end;

    until (l<=1) and p; {продолжаем, пока идут перестановки и

        не произошёл выход за пределы массива}

  end;

  d:=d div 2;  {Уменьшим расстояние между сравниваемыми элементами

      в 2 раза}

end;

Быстрая сортировка

Рассмотрим элемент массива, обладающий следующими свойствами:

• Он не меньше всех элементов массива, стоящих до него
• Он не больше всех элементов массива, стоящих после него

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

  const N=10; {Количество элементов массива}

  var a:  array[1..N] of integer; {массив}

  type

  Pstack=^stack;

  stack=record

    l,r: integer;

    prev: Pstack;

  end;

  var last: Pstack;

             l,r: integer;

  

procedure InStack (l,r: integer);

{Помещение элемента в стек}

  var buf: Pstack;

begin

  buf:=last;

  New (last);

  last^.prev:=buf;

  last^.l:=l;

  last^.r:=r;

end;



function GetStack (var l,r: integer): boolean;

{Выборка элемента из стека, возвращает флаг успеха}

  var buf: Pstack;

begin

  if last<>NIL then

begin

    l:=last^.l;

    r:=last^.r;

    buf:=last;

    last:=last^.prev;

    Dispose (buf);

    GetStack:=true;

  end else GetStack:=false;

end;

  

procedure divide (l,r: integer); 

             l,r: integer;

{Подготовка и собственно разбиение подмассива 

		(индексы элементов l..r)на части}

  var b: integer; {Элемент, по которому происходит разбиение}

      up, down: integer; {Индексы элементов массива:

      			после up все элементы не меньше a

      			до down все элементы не больше a

      				}

      	c: integer;

begin

  b:=a[l];

  up:=l+1;

  down:=r;

  while up

  do begin

    if a[up]then up:=up+1 else 

    			{Если up можно увеличить, мы это делаем}

    if a[down]>b then down:=down-1 else 

    			{Если down можно уменьшить, мы это делаем}

    begin		{Иначе, просто поменяем элементы местами->

    			тогда можно будет изменить и up, и down}

      c:=a[up];

      a[up]:=a[down];

      a[down]:=c;

    end;

  end;

  {Слева от up=down все элементы меньше или равны b, 

  			а справа больше или равны b}

  if a[up]>b then up:=up-1; 

  {Теперь можно поменять местами a[up] и a[l]}

  c:=a[up];

  a[up]:=a[l];

  a[l]:=c;

  {Элемент a[up] является разделителем для метода быстрой сортировки}

  if up-l>r-up then  {Последним поместим в стек индексы части массива 

  					меньшей длины}

  begin

    if up-l>=2 then InStack(l,up-1);{InStack - добавить в стек}

    if r-up>=2 then InStack(up+1,r);

  end else

begin

    if r-up>=2 then InStack(up+1,r);

    if up-l>=2 then InStack(l,up-1);

  end;

end;

.................................

{Собственно сортировка}

  last:=NIL;

  InStack (1,N);

  while (GetStack (l,r)) do {Пока стек не пуст}

    divide (l,r);		{Производим деление для сортировки}