І Я.ФРАНКО
Швидке сортування (сортування Хоара)
Сортування Шелла
Шейкерная сортування
Модифікацією сортування стандартним обміном є шейкернаабо човникове сортування. Тут, як і в методі бульбашки, проводиться попарне порівняння елементів. При цьому перший прохід здійснюється зліва направо, другий — справа наліво і так далі Іншими словами, міняється напрям переглядування елементів списку.
Складність методу стандартного обміну — 0(п2).
У методі Шелла порівнюються не сусідні елементи, а елементи, розташовані на відстані d = [п/2] (де d — крок між порівнюваними елементами, [ ] — ціла частка від числа). Після кожного перегляду крок d зменшується удвічі. На останньому перегляді він скорочується до d = 1.
Наприклад, хай|нехай| даний список, в якому число елементів парне:
{40, 11, 83, 57, 32, 21, 75, 64}.
Список довжини п розбивається на п/2 часток, тобто d= [п/2] = 4.
При першому перегляді порівнюються елементи, віддалені один від одного на d= 4 (мал. 2.7), тобто k1 і к5, к2 і к6 і так далі Якщо кi > ki+d, товідбувається обмін між позиціями i та (i+ d).
Перед другим переглядом вибирається крок d = [d/2] = 2 (мал. 2.8). Потім вибираємо крок d = [d/2] = 1 (мал. 2.9), тобто маємо аналогію з методом стандартного обміну.
Складність методу Шелла — O(0,3n (log2n)2).
У методі швидкого сортування фіксується який-небудь ключ (базовий), відносно якого усі елементи з більшою вагою перекидаються управо, а з меншим — вліво. При цьому увесь список елементів ділиться відносно базового ключа на дві частини. Для кожної частини процес повторюється.
Пояснимо метод на прикладі.
На мал. 2.10 представлений перший етап швидкого сортування. У першому рядку вказана початкова послідовність.
Приймемо перший елемент послідовності за базовий ключ, виділимо його квадратом і позначимо K(0) = 40. Встановимо два покажчики: i і j, з яких i починає відлік ліворуч (i = 1), а j — справа (j = n).
Порівнюємо базовий ключ K(0) і поточний ключ K(j).
Якщо K(0)<= K(j) те встановлюємо j =j - 1 і проводимо наступне порівняння K(0) і K(j) Продовжуємо зменшувати j до тих пір, поки не досягнемо умови K(0)> K(j). Після цього міняємо місцями ключі і K(0) і K(крок 3 на мал. 2.10).
Тепер починаємо змінювати індекс і = і + 1 і порівнювати елементи (i) і К(0). Продовжуємо збільшення і до тих пір, поки не отримаємо умову К(i)> К(0) після чого слідує обмін К(i) і К(див. крок 5). Знову повертаємося до індексу j, зменшуємо його.
Чергуючи зменшення j і збільшення і, продовжуємо цей процес з обох кінців до середини до тих пір, поки не отримаємо і=j (див. крок 7).
На відміну від попередніх розглянутих сортувань вже на першому етапі мають місце два факти: по-перше, базовий ключ K(0)=40 зайняв своє постійне місце в сортованій послідовності; по-друге, усі елементи зліва від будуть менше його, а справа — більше його. Таким чином, після закінчення першого етапу маємо:
Вказана процедура сортування застосовується незалежно до лівої і правої частини масиву.
Складність методу Хоара — 0(nlog2n).
2.1.6. Турнірне сортування
Свою назву це сортування дістало тому, що воно використовується при проведенні змагань, турнірів і олімпіад. Елементи початкової множини представляються листям дерева. Їх попарне порівняння дозволяє визначити максимальний елемент.
Приклад. Дана початкова множина {7, 1, 9, 3, 6, 5, 8}. Здійснити турнірне сортування. Робиться попарне порівняння вершин дерева від низу до верху. Знайдений максимальний елемент поміщається в результуючу множину (мал. 2.11).
В результаті буде отримано впорядковану множину
{9, 8, 7, 6, 5, 3}.
2.1.7. Пірамідальне сортування
Цей тип сортування полягає в побудові пірамідального дерева.
Пірамідальне дерево — це бінарне дерево, що має три властивості :
• у вершині кожної тріади розташовується елемент з більшою вагою;
• листя бінарного дерева розташовується або на одному рівні, або на двох сусідніх (мал. 2.12);
• листя нижнього рівня розташовується лівіше за листя більш високого рівня.
в ході перетворення елементи тріад порівнюються двічі (мал. 2.13), при цьому елемент з більшою вагою перейде вгору, а з меншою — вниз.
Приклад. Дана початкова множина {2, 4, 6, 3, 5, 7}. Метод пірамідального сортування показаний на мал. 2.14.
В результаті буде отримано впорядковану множину
{2, 3, 4, 5, 6. 7}.
Контрольні питання
1. Що розуміється під сортуванням?
2. Які особливості сортування : вставкою, вибором, обміном, Шелла, Хоара, турнірною, пірамідою?
3. Яка основна ідея шейкерной сортування?
4. До якої групи методів відноситься сортування фон Неймана?
5. Що включає поняття складності алгоритму?
6. У чому полягає методика аналізу складності алгоритмів сортування?
(1856 -1916)