РОЗДІЛ 15. ТИПОВІ МЕТОДИ СОРТУВАННЯ МАСИВІВ

До основних типових алгоритмів сортування належать: бульбашкове сортування, сортування за допомогою вибору, сортування вставками.

До основних покращених алгоритмів сортування належать: сортування Шелла, та швидке сортування (quicksort). Найшвидшим алгоритмом є алгоритм швидкого сортування. Його доцільно використовувати для великих об’ємів даних. Якщо дані займають невеликі обсяги можна використовувати типові алгоритми сортування. Розглянемо кожен з алгоритмів більш детально.

15.1. Бульбашкове сортування (bubble sort)

Бульбашкове сортування (bubble sort, сортування методом бульбашки, або просто сортування бульбашкою). Метод бульбашкового сортування є самим простим та малоефективним.

Бульбашкове сортування відноситься до класу обмінних сортувань, тобто до класу сортувань методом обміну. Її алгоритм містить порівняння (тобто багатократні порівняння одних і тих же елементів), що повторюються, і, при необхідності, обмін сусідніх елементів. Елементи поводяться подібно до бульбашок повітря у воді - кожний з них піднімається на свій рівень. Проста форма алгоритму наступна:

void BulbSort(double* a, int l, int r)

{

int i,j;

double tmp;

for(i=l;i<r;i++)

for(j=r;j>i;j--)

if(a[j]<a[i])

{

tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

}

Тут a – вказівка на масив типу double, що підлягає сортуванню, l – нижній індекс, r – верхній індекс масиву. Робота бульбашкового сортування виконується в двох циклах. Зовнішній цикл переглядається до передостаннього елементу масиву (i<r). Це забезпечує розміщення елементів в правильному порядку до кінця виконання функції навіть в найгіршому випадку. Всі порівняння і обміни виконуються у внутрішньому циклі. (Злегка покращувана версія алгоритму бульбашкового сортування завершує роботу, якщо при прогляданні масиву не було зроблено жодного обміну, але це досягається за рахунок додавання ще одного порівняння при кожному проході внутрішнього циклу.)

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

У бульбашковому сортуванні кількість порівнянь завжди одна й та ж, оскільки два цикли for повторюються вказану кількість разів незалежно від того, був список спочатку впорядкований чи ні. Це означає, що алгоритм бульбашкового сортування завжди виконує (n² - n)/2 порівнянь, де п - кількість сортованих елементів. Дана формула виведена на тій підставі, що зовнішній цикл виконується п - 1 раз, а внутрішній виконується в середньому п/2 раз. Добуток цих величин і дає попередній вираз. Зверніть увагу на член п² у формулі. Бульбашкове сортування є алгоритмом порядку п², оскільки час його виконання пропорційний квадрату кількості сортованих елементів. Необхідно визнати, що алгоритм порядку п² не ефективний при великій кількості елементів, оскільки час виконання росте експоненціально залежно від кількості сортованих елементів.

У алгоритмі бульбашкового сортування кількість обмінів в кращому разі рівна нулю, якщо масив вже відсортований. Проте в середньому і гіршому випадках кількість обмінів також є величиною порядку п².

15.2. Сортування за допомогою вибору (choice sort)

При сортуванні за допомогою вибору (сортування вибором, сортування вибірками) з масиву вибирається елемент з найменшим значенням і обмінюється з першим елементом. Потім з тих, що залишилися n - 1 елементів знову вибирається елемент з найменшим ключем і обмінюється з другим елементом, і т.д. Ці обміни продовжуються до двох останніх елементів. Наприклад, якщо застосувати метод вибору до масиву 4, 3, 1, 2, кожен прохід буде виглядати так, як показано нижче:

Початок 4 3 1 2

Прохід 1 1 3 4 2

Прохід 2 1 2 4 3

Прохід 3 1 2 3 4

Нижченаведений код демонструє просте сортування за допомогою вибору:

void ChoiceSort(double* a, int l, int r)

{

int i,j,k,exch;

double tmp;

for(i=l;i<=r;i++)

{

k=i;

exch=0;

tmp=a[i];

for(j=i+1;j<=r;j++)

{

if(a[j]<tmp)

{ k=j;tmp=a[j];exch=1;}

}

if(exch){a[k]=a[i];a[i]=tmp;}

}

}

Як і в бульбашковому сортуванні, зовнішній цикл виконується п - 1 раз, внутрішній - в середньому п/2 раз. Отже, сортування за допомогою вибору вимагає (п² - п)/2 порівняння. Таким чином, це алгоритм порядку п², із-за чого він вважається дуже повільним для сортування великої кількості елементів. Не дивлячись на те, що кількість порівнянь в бульбашковому сортуванні і сортуванні за допомогою вибору однакове, в останній кількість обмінів в середньому випадку набагато менше, ніж в бульбашковому сортуванні.

15.3. Сортування вставками (insert sort)

Сортування вставками – третій і останній з простих алгоритмів сортування. Спочатку він сортує два перші елементи масиву. Потім вставляється третій елемент у відповідну порядку позицію по відношенню до перших двох елементів. Після цього вставляється четвертий елемент в список з трьох елементів. Цей процес повторюється до тих пір, поки не будуть вставлені всі елементи. Наприклад, при сортуванні масив 4, 3, 1, 2 кожен прохід алгоритму виглядатиме таким чином:

Початок 4 3 1 2

Прохід 1 3 4 1 2

Прохід 2 1 3 4 2

Прохід 3 1 2 3 4

Приклад реалізації сортування вставками показаний нижче:

void InsertSort(double* a, int l, int r)

{

int i,j;

double tmp;

for(i=l+1;i<=r;i++)

{

tmp=a[i];

for(j=i-1;(j>=l) && (tmp<a[j]);j--)

a[j+1]=a[j];

a[j+1]=tmp;

}

}

На відміну від бульбашкового сортування і сортування за допомогою вибору, кількість порівнянь в сортуванні вставками залежить від початкової впорядкованості списку. Якщо список вже відсортований, кількість порівнянь дорівнює п - 1; інакше його продуктивність є величиною порядку п².

Взагалі кажучи, в гірших випадках сортування вставками настільки ж неефективне, як бульбашкове сортування і сортування за допомогою вибору, а в середньому вона лише трохи краще. Проте, у сортуванні вставками є переваги. Його поведінка є природною. Іншими словами, воно працює менше всього, коли масив вже впорядкований, і більше всього, коли масив відсортований в зворотному порядку. Тому сортування вставками – ідеальний алгоритм для майже впорядкованих списків.

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