Сортування Шелла. 
Паралельні і розподілені обчислення

Сортування Шелла (англ. Shell sort) — алгоритм сортування, що є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного. Іншими словами — це сортування вставками з попередніми «грубими» проходами. Аналогічний метод удосконалення бульбашкового сортування називається сортування гребінцем.

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

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

• — відсутність потреби в пам’яті під стек;
• — відсутність деградації при невдалих наборах даних — швидке сортування легко деградує до O (n 2), що гірше, ніж найгірше гарантований час для сортування Шелла.

Приклад (рис. 1.3.1):

Нехай дано список: А = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) і.

виконується його сортування методом Шелла, а в якості значень вибрані: 5, 3, 1.

На першому кроці упорядковаются підсписки А, складені з усіх елементів А, що розрізняються на 5 позицій, тобто підсписки А51 = (32,66,40), АБ2 = (95,35,43), Л5,3 = (16,19,93), Л5,4 = (82,75,68), Л5,5 = (24,54).

В отриманому списку на другому кроці знову сортуються підсписки з віддалених на 3 позиції елементів.

Процес завершується звичайної сортуванням вставками отриманого списку.

Рисунок 1.2.4. Сортування Шелла.