Програмна реалізація. 
Необхідність застосування швидких алгоритмів сортування

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

У 1959 році Д. Л. Шелл запропонував замість систематичного включення елемента з індексом i в підмасив попередніх йому елементів (цей спосіб суперечить принципу «балансування», чому і не дозволяє отримати ефективний алгоритм) включати цей елемент в підсписок, що містить елементи з індексами ih, i-2h, i-3h і т.д., де h — деяка натуральна постійна. Таким чином формується масив, в якому h-серії елементів, віддалених один від одного на відстань h, сортуються окремо:

Після того, як розсортовані непересічні h-серії, процес поновлюється з новим значенням h '.

Доведено, що максимальна складність алгоритму Шелла становить O (n5 / 4). Так як.

то цей вид сортування придатний для послідовностей, що мають приблизно до 70 тис. елементів.

Покращення При виборі опорного елемента з даного діапазону випадковим чином гірший випадок стає дуже малоймовірним і очікуваний час виконання алгоритму сортування — O (n lg n).

Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів). Такий вибір також спрямований проти гіршого випадку.

Щоб уникнути досягнення небезпечної глибини рекурсії в гіршому випадку (або при наближенні до нього) можлива модифікація алгоритму, що усуває одну гілку рекурсії: замість того, щоб після поділу масиву викликати рекурсивну процедуру поділу для обох знайдених підмасива, рекурсивний виклик робиться тільки для меншого підмасива, а більший обробляється в циклі в межах цього ж виклику процедури. З точки зору ефективності в середньому разі різниці практично немає: накладні витрати на додатковий рекурсивний виклик і на організацію порівняння довжин підмасива і циклу — приблизно одного порядку. Зате глибина рекурсії ні за яких обставин не перевищить log2n, а в гіршому випадку виродженого поділу вона взагалі буде не більше 2 — вся обробка пройде в циклі першого рівня рекурсії.

Розбивати масив не на дві, а на три частини (див. Dual Pivot Quicksort).

Переваги:

Один з найбільш швидкодіючих (на практиці) з алгоритмів внутрішнього сортування загального призначення.

Простий в реалізації.

Потребує лише додаткової пам’яті для своєї роботи. (Не покращений рекурсивний алгоритм у гіршому випадку пам’яті).

Добре поєднується з механізмами кешування і віртуальної пам’яті.

Існує ефективна модифікація (алгоритм Седжвіка) для сортування рядків — спочатку порівняння з опорним елементом тільки за нульовим символу рядка, далі застосування аналогічної сортування для «більшого» і «меншого» масивів теж за нульовим символу, і для «рівного» масиву по вже першого символу .

Недоліки:

Сильно деградує за швидкістю (до) при невдалих виборах опорних елементів, що може трапитися при невдалих вхідних даних. Цього можна уникнути, використовуючи такі модифікації алгоритму, як Introsort, або вероятностно, вибираючи опорний елемент випадково, а не фіксованим чином.

Наївна реалізація алгоритму може привести до помилки переповнення стека, так як їй може знадобитися зробити вкладених рекурсивних викликів. У покращених реалізаціях, в яких рекурсивний виклик відбувається тільки для сортування меншою з двох частин масиву, глибина рекурсії гарантовано не перевищить.

Нестійкий — якщо потрібна стійкість, доводиться розширювати ключ.

Розглянемо роботу процедури для масиву a [0] … a [6] і опорного елемента p = a [3].

Рисунок 3.8 — Приклад роботи процедури сортування.