• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Метод Шелла

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

Метод полягає в тому, що таблиця, яка впорядковується, розділяється на групи елементів, кожна з яких упорядковується методом простих включень. У процесі впорядкування розміри таких груп збільшуються доти, поки всі елементи таблиці не ввійдуть у впорядковану групу. Вибір чергової групи для сортування і її розташування всередині таблиці здійснюється так, щоб можна було використовувати попередню впорядкованість. Групою таблиці називають послідовність елементів, номери яких утворять арифметичну прогресію з різницею 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 – Приклад сортування методом Шелла.

У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з 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 – Приклад сортування методом бульбашки.

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

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

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

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

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

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

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 1348