Назад (Информатика).

Алгоритм обменной сортировки

Простая обменная сортировка [в просторечии называемая "методом пузырька"] для массива M[0], M[1], ..., M[n-1] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента [M[n-1] и M[n-2]]. Если выполняется условие M[n-2] > M[n-1], то значения элементов меняются местами. Процесс продолжается для M[n-2] и M[n-3] и т.д., пока не будет произведено сравнение M[1] и M[0]. Понятно, что после этого на месте M[0] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются M[2] и M[1]. И так далее. На последнем шаге будут сравниваться только текущие значения M[n-1] и M[n-2]. Понятна аналогия с пузырьком, поскольку наименьшие элементы [самые "легкие"] постепенно "всплывают" к верхней границе массива. Ниже приведен пример реализации алгоритма простой обменной сортировки:

Общий алгоритм

function Grade (Array[], LengthOfArray) {
     if (LengthOfArray < 2) then return Array[]
     else {
          LimitIndex:=1;
          while (LimitIndex < LengthOfArray) do {
               CurrentIndex:= LengthOfArray-1;
               while (CurrentIndex > LimitIndex) do {
                    if (Array[CurrentIndex-1] > Array[CurrentIndex]) then {
                         Temp:= Array[CurrentIndex-1];
                         Array[CurrentIndex-1]:= Array[CurrentIndex];
                         Array[CurrentIndex]:=Temp;
                    }
                    CurrentIndex:= CurrentIndex-1;
               }
               LimitIndex:= LimitIndex+1;
          }
          return Array[];
     }
}

Pascal

program primer;
const n=5;
var a: array [1..n] of integer;
     i, currentIndex, limitIndex, temp: integer;
begin
     // заполнение массива случайными целыми числами от 10 до 99
     randomize;
     for i:=1 to n do begin
          a[i]:=trunc((99-10)*random+10);
     end;

     // вывод исходного массива
     write('Исходный массив: ');
     for i:=1 to n do begin
          write ('a[', i, ']=>', a[i]:3, '; ');
     end;
     writeln;

     // обменная сортировка
     if not (n<2) then begin
     limitIndex:=1;
     while (limitIndex<=n) do begin
               currentIndex:=n;
               while (currentIndex>limitIndex) do begin
                    if (a[currentIndex-1]>a[currentIndex]) then begin
                         temp:=a[currentIndex-1];
                         a[currentIndex-1]:=a[currentIndex];
                         a[currentIndex]:=temp;
                    end;
                    dec(currentIndex);
               end;
               inc(limitIndex);
          end;
     end;

     // вывод отсортированного массива
     write('Отсортированный массив: ');
     for i:=1 to n do begin
          write ('a[', i, ']=>', a[i]:3, '; ');
     end;
     writeln;writeln;
end.