Приклад 7.11

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

1. Установити лічильник ітерацій рівним одиниці.
2. Для елементів масиву, від останнього до елемента з індексом, що дорівнює поточному значенню лічильника ітерацій, повторювати такі дії.
   2.1. Якщо поточний елемент більший за попередній, поміняти ці елементи місцями.
   2.2. Перейти до попереднього елемента.
3. Збільшити лічильник ітерацій. Якщо значення лічильника дорівнює кількості елементів масиву, завершити сортування.

Program EX7_10;
var n, i, j, k: integer;
a: array [1..10] of integer;
tmp: integer;
begin
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: =1 to n do
write(a[i], ' ');
writeln;
writeln('sort process');
for i: =2 to n do
for j: =n downto i do
if a[j]< a[j-1] then
begin
tmp: =a[j];
a[j]: =a[j-1];
a[j-1]: =tmp;
for k: =1 to n do
write(a[k], ' ');
writeln;
end;
writeln('sorted array');
for i: =1 to n do
write(a[i], ' ');
end.

Рис. 7.12. Результати роботи програми ех7_10. Сортування масиву методом обміну

Демонстрація прикладу

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

Удосконалені методи сортування масиву використовують значно меншу кількість операцій порівняння та перестановок елементів. Детальний аналіз алгоритмів сортування зроблено у [5, 12, 13]. Розглянемо один з удосконалених методів сортування масиву.