Сортування методом обміну

Базовою операцією в цьому методі є порівняння двох сусідніх елементів масиву. Якщо їх розташування суперечить умові впорядкування, вони міняються місцями. Послідовне застосування такої операції до всіх пар елементів масиву, від останньої пари до першої, дозволить виявити найменший елемент в першій пози­ції. Друга назва цього метода - бульбашкове сортування — пояснюється схожістю процесу обміну місцями сусідніх елементів зі спливанням більшої буль­башки. Під час сортування методом обміну впорядкованою буде ліва частина масиву, а щойно описаний процес повторюється для правої частини, котра на кожній ітерації методу зменшуватиметься на один елемент.

Приклад3

Розглянемо алгоритм сортування методом обміну та його реалізацію мовою Pascal.

1.Установити лічильник ітерацій рівним одиниці.

2.Для елементів масиву, від останнього до елемента з індексом, що дорівнює поточному значенню лічильника ітерацій, повторювати такі дії.

2.1.Якщо поточний елемент більший за попередній, поміняти ці елементи місцями.

2.2.Перейти до попереднього елемента.

3. Збільшити лічильник ітерацій. Якщо значення лічильника дорівнює кількості
елементів масиву, завершити сортування.

program ex6_3; {сортування обміном}

uses crt;

var n,i,j,k:integer; {кількість та індекси елементів}

а:аrrау[1..10] of integer;

tmp:integer; {допоміжний елемент для обміну}

Begin

clrscr;

randomize;

writeln('exchange sort');

writeln(‘enter number of the components (<=10)’);

readln(n);

for i:=2 to n do {генерувати масив}

a[i]:=random(30);

writeln(‘generated array’);

for i:=l to n do {вивести згенерований масив}

write( a[i].' ');

writeln;

writeln(‘sort process’);

for i:=2 to n do {сортувати методом обміну}

for j:=n downto і do

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

begin {поміняти елементи місцями}

tmp:=a[j];

a[j];=a[j-l];

a[j-l]:=tmp;

{виведення проміжних результатів}

for k:=l to n do

write(a[k].' ');

writeln;

end;
writeln('sorted array');
for i:=l to n do {вивести відсортований масив}

write(a[i],' ');

readln;

End.

Алгоритми сортування масивів методами вибору, вставки та обміну не потребують додаткової оперативної пам'яті. Час виконання розглянутих алгоритмів сортування пропорційний кількості операцій порівняння або перестановок елементів. Сортування n-елементного масиву методом вибору потребує n²/2 операцій і порівняння та п операцій обміну елементів. Метод сортування вставкою потребує n²/4 операцій порівняння та стільки ж операцій обміну, а метод сортування обміном — п/2 операцій порівняння та п²/2 операцій обміну. Отже, методи вставки та вибору за характеристиками приблизно еквівалентні, проте метод обміну поступається перед ними швидкодією.

Удосконалені методи сортування масиву використовують значно меншу кількість операцій порівняння та перестановок елементів.

Розглянемо один з удосконалених методів сортування масиву.