Метод Шелла

Подальшим розвитком методу сортування з включеннями є сортування методом Шелла, яке інакше називається сортуванням включеннями з відстанню, що зменшується.

Метод полягає в тому, що таблиця, яка впорядковується, розділяється на групи елементів, кожна з яких упорядковується методом простих включень. У процесі впорядкування розміри таких груп збільшуються доти, поки всі елементи таблиці не ввійдуть у впорядковану групу. Вибір чергової групи для сортування і її розташування всередині таблиці здійснюється так, щоб можна було використовувати попередню впорядкованість. Групою таблиці називають послідовність елементів, номери яких утворять арифметичну прогресію з різницею h (h називають кроком групи). На початку процесу впорядкування вибирається перший крок групи h₁, що залежить від розміру таблиці. Шелл запропонував брати

h₁=[h/2], a h_i=h((i-1)/2).

У більш пізніх роботах Хіббард показав, що для прискорення процесу доцільно визначити крок h₁ за формулою:

h₁=2**k+1, де 2**k<n<=2**(k+1).

Після вибору h₁ методом простих включень впорядковуються групи, що містять елементи з номерами позицій і, i+h₁, i+2*h₁, …, i+m_i*h₁.

При цьому i=1,2,..., h₁; m[і] – найбільше ціле, що задовольняє нерівність i+m[i]*h_i <= n.

Потім вибирається крок h₂ <h₁ і впорядковуються групи, що містять елементи з номерами позицій і, i+h₂,…, i+m[i]*h₂.Ця процедура з усе зменшуваними кроками продовжується доти, поки черговий крок h[l] стане рівним одиниці (h₁>h₂>.. .>h_l). Цей останній етап являє собою впорядкування всієї таблиці методом включень. Але оскільки вихідна таблиця впорядковувалася окремими групами з послідовним об'єднанням цих груп, то загальна кількість порівнянь значно менша, ніж n/4, необхідна при методі включень. Кількість операцій порівняння пропорційна n*(log₂(n))**2.

Застосування методу Шелла до масиву, використаного в наших прикладах, показано в таблиці 2.

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

Початковий стан масиву	8 23 5 65 44 33 1 6
Фаза 1 (сортуються елементи, відстань між якими чотирьом)	8 23 5 65 44 33 1 6
8 23 5 65 44 33 1 6
8 23 1 65 44 33 5 6
8 23 1 6 44 33 5 65
Фаза2 (сортуються елементи, відстань між якими двом)	1 23 8 6 44 33 5 65
1 23 8 6 44 33 5 65
1 23 8 6 5 33 44 65
1 23 5 6 8 33 44 65
1 6 5 23 8 33 44 65
1 6 5 23 8 33 44 65
1 6 5 23 8 33 44 65
Фаза3 (сортуються елементи, відстань між якими одному)	1 6 5 23 8 33 44 65
1 5 6 23 8 33 44 65
1 5 6 23 8 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65

У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з t відстаней між елементами h₁, h₂, ..., h_t, для яких виконуються умови h₁ = 1 і h(i+1)< h_i При правильно підібраних t і h складність алгоритму Шелла є Θ (n(1.2)), що істотно менша за складність простих алгоритмів сортування.

Блок-схема методу Шелла подана на рисунку 15. У ньому використано змінні:

а[] – масив, який необхідно відсортувати,

t – допоміжна змінна того ж типу, що і масив,

n – розмірність масиву.

Рисунок 15 – Блок-схема методу Шелла.

4 Обмінне сортування

Просте обмінне сортування (≪методом бульбашки≫) для масиву a a[1], a[2], ..., а[n] працює таким чином. Починаючи з кінця масиву порівнюються два сусідні елементи (а[n] і а[n-1]). Якщо виконується умова a[n-1 ]>a[n], то значення елементів міняються місцями. Процес продовжується для a[n-l] і а[n-2] і т.ін., поки не буде здійснено порівняння а[2] і а[1]. Зрозуміло, що після цього на місці а[1] виявиться елемент масиву з якнайменшим значенням. На другому кроці процес повторюється, але останніми порівнюються а[3] і а[2]. І так далі. На останньому кроці порівнюватимуться тільки поточні значення а[n] і а[n-1]. Зрозуміла аналогія з бульбашкою, оскільки найменші елементи (≪найлегші≫) поступово ≪спливають≫ до верхньої межі масиву. Приклад сортування методом бульбашки показаний в таблиці 3.

Для методу простого обмінного сортування потрібна кількість порівнянь nх(n-1)/2, мінімальна кількість пересилань 0, а середня і максимальна кількість пересилань - Θ (n²).

Блок-схема методу бульбашки поданана рисунку 16.

Рисунок 16 – Алгоритм сортування методом бульбашки.

Таблиця 3 – Приклад сортування методом бульбашки.

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	8 23 5 65 44 33 1 6
8 23 5 65 44 1 33 6
8 23 5 65 1 44 33 б
8 23 5 1 65 44 33 6
Продовження таблиці 3 – Приклад сортування методом бульбашки.
	8 23 1 5 65 44 33 6
8 1 23 5 65 44 33 6
1 8 23 5 65 44 33 6
Крок 2	1 8 23 5 65 44 6 33
1 8 23 5 65 6 44 33
1 8 23 5 6 65 44 33
1 8 23 5 6 65 44 33
1 8 5 23 6 65 44 33
1 5 8 23 6 65 44 33
Крок 3	1 5 8 23 6 65 33 44
1 5 8 23 6 33 65 44
1 5 8 23 6 33 65 44
1 5 8 6 23 33 65 44
1 5 6 8 23 33 65 44
Крок 4	1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Крок 5	1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Крок 6	1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Крок 7	1 5 6 8 23 33 44 65

Метод бульбашки допускає три прості вдосконалення. По-перше, як показує таблиця 3, на чотирьох останніх кроках розташування значень елементів не змінювалося (масив виявився вже впорядкованим). Тому, якщо на деякому кроці не було вироблено жодного обміну, то виконання алгоритму можна припиняти. По-друге, можна запам'ятовувати якнайменше значення індекса масиву, для якого на поточному кроці виконувалися перестановки.

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

На цих спостереженнях заснований метод шейкерного сортування (ShakerSort). При його застосуванні на кожному наступному кроці змінюється напрямок послідовного перегляду. У результаті, на одному кроці ≪спливає≫ черговий найлегший елемент, а на іншому ≪тоне≫ черговий найважчий. Приклад шейкерного сортування наведений у таблиці 4.

Шейкерне сортування дозволяє скоротити кількість порівнянь (за оцінкою Кнута середньою кількістю порівнянь є (n2 - n(const + ln n)), хоча порядком оцінки як і раніше залишається n2. Кількість посилань загалом не змінюється. Шейкерне сортування рекомендується використовувати в тих випадках, коли відомо, що масив ≪майже впорядкований≫.

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Метод простого включення	\|	Сортування вибором

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.