Сортування простим обміном

Наведений нижче алгоритм  сортування простим обміном заснований на принципі порівняння й обміну пари сусідніх елементів доти, поки не будуть відсортовані всі елементи. Сутність методу полягає у тому, що на кожному кроці порівнюються пари сусідніх елементів. Якщо “лівий” елемент більший за “правий”, то вони міняються місцями. Тобто, здійснюється впорядкування кожної пари елементів. Порівняння здійснюємо, починаючи з кінця масиву в зворотному природному порядку напрямку. В результаті елементи з малими значеннями будуть рухатись в бік початку масиву.

Якщо ми для розмаїтості будемо розглядати масив, розташований вертикально, і, уявляти  елементи пухирцями в резервуарі з водою, що володіють «вагами», які повідають їхнім ключам, то кожен прохід по масиві проводить до «спливання» пухирця на відповідній його вазі рівень.

Застосування методу розглянемо на прикладі впорядкування масиву з 10 елементів. Елементи, що переміщувались вліво, виділимо кольором.

Вихідний масив:

44  55  12  42  94  18  06  67  32  13

Після першого кроку:

06  44  55  12  42  94  18  13  67  32

Після другого кроку:

06  12  44  55  13  42  94  18  32  67

Після останнього кроку:

06  12  13  18  32  42  44  55  67  94

Процедура для запису алгоритму має вигляд:

procedure bubblesort (var a: massiv);

var

i,j: integer;

x: integer;

n1,n: integer;

begin

{границі масиву}

n1:=low(a);

n:= high (a);

{впорядкування}

for i:= n1 to n-1 do

  for j:= n downto i+1 do

  if a[j]<a[j-1] then

  begin

  x:=a[j];

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

  a[j-1]:=x;

  end;

end;

Число порівнянь для сортування даним методом дорівнює:

C=1/2 (n² - n),

а кількість пересилань

M_min  = 0, 

M_ср = 3/4 (n² - n), 

M_max  = 3/2 (n² - n).