Сортування Шелла — це алгоритм сортування, що є узагальненням сортування включенням. Він був розроблений Дональдом Шеллом у 1959 році.
Принцип роботи
Сортування Шелла працює шляхом багаторазового застосування сортування включенням із різними інтервалами (або кроками). Інтервал визначається послідовністю Шелла, яка зазвичай є послідовністю, що зменшується двійково або націло.
Вибір послідовності Шелла впливає на ефективність алгоритму. Послідовності, наприклад, послідовність Седжвіка або послідовність Кнута, зазвичай забезпечують хорошу продуктивність.
Алгоритм
- Виберіть послідовність Шелла.
- Для кожного інтервалу h послідовності Шелла:
- Поділіть масив на h підмасивів.
- Застосуйте сортування включенням до кожного підмасиву.
Псевдокод
сортувати_шелла(масив, послідовність_шелла):
for h in послідовність_шелла:
for i in range(h):
сортувати_включенням(масив[i::h])
Приклад
Розглянемо наступний масив: [5, 3, 1, 2, 4]. Використовуючи послідовність Шелла h = [2, 1], ми можемо відсортувати масив таким чином:
- При h = 2:
- Розділіть масив на два підмасиви: [5, 3] і [1, 2, 4].
- Застосуйте сортування включенням до кожного підмасиву: [3, 5] і [1, 2, 4].
- При h = 1:
- Це фактично сортування включенням для всього масиву.
- Застосуйте сортування включенням до масиву [3, 5, 1, 2, 4].
Отримаємо відсортований масив: [1, 2, 3, 4, 5].
Складність
Складність сортування Шелла в середньому становить O(n log^2 n), а в гіршому випадку — O(n^2).
Переваги
- Просте у реалізації.
- Працює добре для середніх і великих масивів.
- Може бути налаштований за допомогою різних послідовностей Шелла.
Недоліки
- Не так ефективний, як інші алгоритми сортування, такі як швидке сортування або злиття сортування.
- Не стабільне, тобто елементи з однаковими значеннями можуть змінювати порядок.
Сортування Шелла — це ефективний алгоритм сортування, який поєднує простоту сортування включенням з узагальненням інтервалів. Він є гарним вибором для середніх і великих масивів і може бути налаштований за допомогою різних послідовностей Шелла.
Часто задаються питання
- Чи є сортування Шелла стабільним? Ні, не є.
- Яка рекомендована послідовність Шелла? Послідовність Седжвіка або послідовність Кнута.
- Який часовий проміжок сортування Шелла? O(n log^2 n) у середньому і O(n^2) у гіршому випадку.
- Чи є сортування Шелла швидшим, ніж швидке сортування? Ні, швидке сортування зазвичай швидше.
- Для яких типів даних можна використовувати сортування Шелла? Для будь-якого типу даних, який підтримує порівняння.
0 Коментарі
Останній коментар
Коментарів ще немає