Алгоритм сортування оболонки з прикладом

Що таке сортування за допомогою Shell?

Сортування Шелла, також відоме як метод Шелла, — це ефективний алгоритм сортування на основі порівняння на місці. Названий на честь Дональда Шелла, який запропонував цю ідею в 1959 році, він є узагальненим розширенням сортування вставками, яке долає його квадратичну поведінку на розсіяних даних.

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

Цей проміжок, інтервал, відповідає обраній послідовності, такій як оригінал Шелла, Кнута, Гіббарда або Седжвіка. Оригінал Шелла є n/2, n/4, ..., 1.

Алгоритм сортування оболонки

Крок 1) Ініціалізуйте значення інтервалу h = n/2, де n – розмір масиву.

Крок 2) Розмістіть усі елементи в межах інтервалу h у підсписку.

Крок 3) Відсортуйте кожен підсписок за допомогою сортування вставками.

Крок 4) Встановити новий інтервал h = h/2.

Крок 5) Якщо h > 0, поверніться до кроку 2. В іншому випадку перейдіть до кроку 6.

Крок 6) Отриманий масив тепер повністю відсортований.

Як працює Shell Sort

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

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

Робота алгоритму сортування Shell з прикладом

Давайте відсортуємо масив нижче за допомогою Shell Sort.

Крок 1) Розмір масиву дорівнює 8, тому початкове значення інтервалу h = 8/2 = 4.

Крок 2) Групувати елементи з інтервалом у чотири позиції. Підсписки: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Крок 3) Відсортуйте кожен підсписок за допомогою сортування вставками. Тимчасова змінна зберігає значення, яке розміщується, поки елементи зміщуються. Після заміни масив виглядає ось так.

Крок 4) Зменште інтервал. Новий інтервал буде h = 4/2 = 2.

Крок 5) Оскільки 2 > 0, поверніться до кроку 2 та згрупуйте елементи з відстанню між ними дві позиції: {1, 5, 8, 7} та {4, 2, 6, 3}.

Відсортуйте перший підсписок. Масив стане таким:

Після сортування другого підсписку:

Знову зменште інтервал до h = 2/2 = 1. З проміжком в одиницю, Shell Sort виконує остаточний прохід сортування вставками по всьому масиву, як показано нижче.

Крок 6) Повторне ділення інтервалу дає 0. Масив тепер повністю відсортований:

Псевдо-Code для сортування по Шеллу

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Програма сортування Shell на C/C++

Вхідний сигнал:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

вихід:

Sorted Output:

1 2 3 4 5 6 7 8

Приклад сортування оболонки в Python

Вхідний сигнал:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

вихід:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Застосування Shell Sort

Сортування оболонкою досі зустрічається в сучасних системах, де має значення простір стеку або простота.

• Команда ядро Linux використовує сортування оболонки (Shell Sort) у місцях, де важливо уникнути стеку викликів.
• Вбудована бібліотека C uClibc використовує сортування Shell для збереження низького використання пам'яті.
• bzip2 використовує сортування Shell, щоб уникнути глибокої рекурсії під час сортування блоків.
• Вбудоване програмне забезпечення надає перевагу сортуванню Shell для невеликих наборів даних, де рекурсія обмежена.

Переваги та недоліки сортування Shell

Аналіз складності сортування оболонки

Часова складність сортування Shell

Часова складність сортування Shell залежить від використаної послідовності проміжків.

У найкращому випадку, коли масив вже майже впорядкований, кожен прохід потребує лише логарифмічної кількості перевірок, що дає O(n log n).

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

1. Складність у найкращому випадку: O(n log n)
2. Середня складність випадку: від O(n log n) до O(n^(4/3)) залежно від послідовності прогалин
3. Складність у найгіршому випадку: O(n^2) з оригінальною послідовністю Шелла

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

Складність простору сортування оболонки

Shell Sort не потребує допоміжних масивів, тому просторова складність становить O(1) незалежно від розміру вхідних даних, що є однією з її найсильніших практичних переваг.

Поширені запитання