Алгоритм сортування оболонки з ПРИКЛАДОМ
Сара Чен
Що таке Shell Sort
Метод Shell, або сортування Shell у структурі даних, є ефективним алгоритмом сортування порівняння на місці. Він названий на честь Дональда Шелла, коли він запропонував початкову ідею ще в 1959 році. Shell sort є узагальненим розширенням алгоритму сортування вставкою.
Фундаментальна ідея цього алгоритму сортування полягає в групуванні елементів, які розташовані далеко один від одного, і сортуванні їх відповідно. Потім поступово зменшуйте проміжок між ними. Сортування оболонки долає середню складність випадку сортування вставкою шляхом порівняння та обміну елементами, які знаходяться далеко.
Цей розрив, відомий як інтервал, скорочується відповідно до деяких оптимальних послідовностей розривів. Час роботи сортування оболонки також залежить від цих послідовностей. Існує кілька послідовностей розривів, таких як вихідна послідовність Шелла, формула Кнута, прирости Гіббарда тощо. Оригінальна послідовність розривів Шелла – n/2, n/4, n/8, ……….1
Алгоритм сортування оболонки
Кроки або процедура для алгоритму сортування оболонки такі:
Крок 1) Ініціалізуйте значення інтервалу, h = n/2. (У цьому прикладі n — розмір масиву)
Крок 2) Розмістіть усі елементи на відстані інтервалу h у підсписку.
Крок 3) Відсортуйте ці підсписки за допомогою сортування вставкою.
Крок 4) Встановити новий інтервал, h=h/2.
Крок 5) Якщо h>0, перейдіть до кроку 2. Інакше перейдіть до кроку 6.
Крок 6) Результатом буде відсортований масив.
Як працює Shell Sort
Під час сортування вставкою елементи переміщуються лише на одну позицію за раз. Навпаки, сортування оболонки ділить масив на менші частини на основі значення інтервалу та виконує сортування вставкою на цих частинах.
Поступово значення інтервалу зменшується, а розмір розділених частин збільшується. Оскільки фрагменти попередньо сортуються окремо, об’єднання цих фрагментів вимагає менше кроків, ніж сортування вставки.
Наступний GIF показує демонстрацію сортування оболонки. У цій демонстрації червоне та синє позначені значення порівнюються та міняються місцями на основі сортування вставкою. Потім інтервал зменшується, і сортування оболонки ініціює сортування вставкою в ці майже відсортовані дані.
Робота алгоритму сортування Shell
Давайте розглянемо наступний приклад алгоритму сортування оболонки. У цьому прикладі ми відсортуємо наступний масив за допомогою сортування оболонки:
Крок 1) Тут розмір масиву дорівнює 8. Таким чином, значення інтервалу буде h = 8/2 або 4.
Крок 2) Тепер ми будемо зберігати всі елементи на відстані 4. Для нашого випадку це підсписки: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Крок 3) Тепер ці підсписки буде відсортовано за допомогою сортування вставкою, де тимчасова змінна використовується для порівняння обох чисел і сортування відповідно.
Після операцій обміну масив матиме такий вигляд:
Крок 4) Тепер ми зменшимо початкове значення інтервалу. Новий інтервал буде h=h/2 або 4/2 або 2.
Крок 5) Якщо 2>0, ми перейдемо до кроку 2, щоб зберегти всі елементи на відстані 2. На цей час підсписки:
{1, 5, 8, 7}, {4, 2, 6, 3}
Потім ці підсписки будуть відсортовані за допомогою сортування вставкою. Після порівняння та заміни першого підсписку масив буде таким.
Після сортування другого підсписку вихідний масив буде таким:
Потім знову інтервал буде зменшено. Тепер інтервал буде h=h/2 або 2/1 або 1. Отже, ми будемо використовувати алгоритм сортування вставкою, щоб сортувати змінений масив.
Нижче наведено покрокове процедурне зображення сортування вставкою.
Інтервал знову ділиться на 2. До цього часу інтервал стає 0. Отже, ми переходимо до кроку 6.
Крок 6) Оскільки інтервал дорівнює 0, масив сортується за цим часом. Відсортований масив -
Псевдокод
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; 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
Ось важливі застосування Shell Sort:
- Shell sort використовується в ядро Linux оскільки він не використовує стек викликів.
- Бібліотека uClibc використовує сортування Shell.
- Компресор bzip2 використовує сортування Shell, щоб зупинити перевищення рекурсії.
Переваги та недоліки Shell Sort
| Переваги | Недоліки |
|---|---|
| Виклик стека не потрібен. | Неефективно для великих масивів. |
| Легка реалізація. | Неефективний для широко розповсюджених елементів. |
| Ефективний для менш широко розташованих елементів. |
Аналіз складності сортування оболонки
Часова складність сортування Shell
Часова складність алгоритму сортування оболонки становить O(n^2). Аргументація така:
Для найкращого сценарію загальна кількість тестів для всіх інтервалів, коли масив був попередньо впорядкований, дорівнює log n. Таким чином, складність буде O(n*log n).
Для найгіршого сценарію давайте розглянемо, що масив складається таким чином, що елементи потребують найбільшої кількості порівнянь. Тоді всі елементи не будуть порівнюватися та перемикатися до останньої ітерації. Отже, загальна кількість порівнянь, необхідних для остаточного приросту, становить O(n^2).
Підсумовуючи, часові складності будуть
- Найкращий варіант складності: O(n*log n)
- Середня складність випадку: O(n*log n)
- Найгірша складність: O(n^2)
Складність часу виконання сортування оболонки сильно залежить від використовуваних послідовностей збільшення проміжків. Однак найкраща послідовність приросту для сортування оболонки все ще невідома.
Складність простору сортування оболонки
У цьому сортуванні для порівняння нам не потрібен додатковий допоміжний простір. Таким чином, просторова складність такого роду алгоритмів дорівнює O(1).
