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

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

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

Застосування методу розглянемо на прикладі впорядкування масиву з 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

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

procedurebubblesort (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).

Сортировка включением - вставкой

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

Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением.

При использовании линейного поиска вычислительная сложность сортировки вклю-чением составляет O(N*N), а при использовании двоичного поиска- O(N*Log2N) (имеется в виду логарифм по основанию 2).

Пример. Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.

program Sort_Include1;

var A: array[1..100] of integer;

N, i, k, x: integer;

begin

write('количество элементов массива ');

read(N);

read(A[1]); {for i: =1 to n do read(A[i]); }

{k - количество элементов в упорядоченной части массива}

for k: =1 to n-1 do

begin

read(x); {x: =A[k+1]; }

i: =k;

while (i> 0)and(A[i]> x) do

begin

A[i+1]: =A[i];

i: =i-1;

end;

A[i+1]: =x;

end;

for i: =1 to n do write(A[i], ' '); {упорядоченный массив}

end.

Пример. Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском.

program Sort_Include2;

var A: array[1..100] of integer;

N, i, k, x, c, left, right: integer;

begin

write('количество элементов массива '); read(N);

read(A[1]); {for i: =1 to n do read(A[i]); }

{k - количество элементов в упорядоченной части массива}

for k: =1 to n-1 do

begin

read(x); {x: =A[k+1]; }

left: =1; right: =k;

{левая и правая граница фрагмента для поиска}

while left=A[c] then left: =c

{берем правую половину с серединой}

else right: =c-1; {берем левую половину без середины}

end;

if x> =A[left] then left: =left+1;

{сдвигаем на 1 вправо часть массива, освобождая место для включения x}

for i: =k downto left do A[i+1]: =A[i];

A[left]: =x;

end;

for i: =1 to n do write(A[i], ' '); {упорядоченный массив}

end.