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

При сортуванні масиву а[1], а[2],..., a[n] методом простого вибору серед всіх елементів знаходиться елемент з якнайменшим значенням а[і], і а[1] і а[і] обмінюються значеннями. Потім цей процес повторюється для одержуваних підмасивів а[2], а[3],..., а[n]... a[j], a[j+1],..., а[n] до тих пір, поки ми не дійдемо до підмасиву а[n], що містить до цього моменту найбільше значення. Робота алгоритму ілюструється прикладом в таблиці 5.

Для методу сортування простим вибором необхідна кількість порівнянь – n[n-1)/2. Порядок необхідної кількості посилань (включаючи ті, які потрібні для вибору мінімального елемента) у гіршому разі складає Θ (n²). Проте порядок середньої кількості пересилань є (n ln n), що у ряді випадків робить цей метод одним із найкращих.

Таблиця 5 – Приклад сортування простим вибором.

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	1 23 5 65 44 33 8 6
Крок 2	1 5 23 65 44 33 8 6
Крок 3	1 5 6 65 44 33 8 23
Крок 4	1 5 6 8 44 33 65 23
Крок 5	1 5 6 8 33 44 65 23
Крок 6	1 5 6 8 23 44 65 33
Крок 7	1 5 6 8 23 33 65 44
Крок 8	1 5 6 8 23 33 44 65

Функція сортування вибором виглядає так:

void sort_vyb()

{

Int i,j a[10],t;

for (i=0; i<10-1; i++

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

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

{

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

6 Сортування поділом (Хоара)

Метод сортування поділом був запропонований Чарльзом Хоаром 1962 року. Цей метод є розвитком методу простого обміну і настільки ефективний, що його почали називати ≪методом швидкого сортування - Quicksort≫.

Основна ідея алгоритму полягає в тому, що випадковим чином вибирається деякий елемент масиву х, після чого масив є видимим зліва, поки не зустрінеться елемент а[і] такий, що а[і]>х, а потім масив є видимим справа, поки не зустрінеться елемент a[j] такий, що a[j]<x. Ці два елементи міняються місцями, і процес перегляду, порівняння і обміну продовжується, поки ми не дійдемо до елемента х. У результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть менші від х, і праву із значеннями ключів, більшими від х. Далі процес рекурсивно продовжується для лівої і правої частин масиву до тих пір, поки кожна частина не міститиме лише один елемент (рисунок 17). Зрозуміло, що, як завжди, рекурсію можна замінити ітераціями, якщо запам'ятовувати відповідні індекси масиву. Прослідкуємо цей процес на прикладі нашого стандартного масиву (таблиця 6).

Таблиця 6 – Приклад швидкого сортування.

Початковий стан масиву	8 23 5 65 |44| 33 1 6
Крок 1 (як х вибирається а[5])	8 23 5 6 44 33 1 65
8 23 5 6 1 33 44 65
Крок 2 (у підмасиві а[1], а[5] як х вибирається а[3])	8 23 |5| 6 1 33 44 65
1 23 5 6 8 33 44 65
1 5 23 6 8 33 44 65
Крок 3 (у підмасиві а[3], а[5] як х вибирається а[4])	1 5 23 |6| 8 33 44 65
1 5 8 6 23 33 44 65
Крок 4 (у підмасивах а[3], а[4] вибирається а[4])	1 5 8 |6| 23 33 44 65
1 5 6 8 23 33 44 65

Рисунок 17 – Блок-схема рекурсивного методу Хоара

Алгоритм недаремно називається швидким сортуванням, оскільки для нього оцінкою кількості порівнянь і обмінів є Θ (n log n). Насправді, в більшості утиліт, що виконують сортування масивів, використовується саме цей алгоритм.