І Я. Франко

Швидке сортування (сортування Хоара)

Сортування Шелла

Шейкерная сортування

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

Складність методу стандартного обміну — 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 > k_i+d, товідбувається обмін між позиціями i та (i+ d).

Перед другим переглядом вибирається крок d = [d/2] = 2 (мал. 2.8). Потім вибираємо крок d = [d/2] = 1 (мал. 2.9), тобто маємо аналогію з методом стандартного обміну.

Складність методу Шелла — O(0,3n (log2n)²).

У методі швидкого сортування фіксується який-небудь ключ (базовий), відносно якого усі елементи з більшою вагою перекидаються управо, а з меншим — вліво. При цьому увесь список елементів ділиться відносно базового ключа на дві частини. Для кожної частини процес повторюється.

Пояснимо метод на прикладі.

На мал. 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)

Дата добавления: 2013-12-14