1. теорія
2. Реалізація

Наше деловое партнерство www.banwar.org

Метод, запропонований Дональдом Л. Шеллом, є нестійкою сортуванням за місцем. Ефективність методу Шелла пояснюється тим, що можна зсунути елементи швидко потрапляють на потрібні місця. Середній час для сортування Шелла дорівнює O (n 1.25), для гіршого випадку оцінкою є O (n 1.5). Подальші властивості см. В книжці Кнута [1998] .

теорія

На рис. 2.2 (a) було наведено приклад сортування вставками. Ми спочатку виймали 1, потім зсовували 3 і 5 на одну позицію вниз, після чого вставляли 1. Таким чином, нам були потрібні два зсуви. Наступного разу нам потрібно ще два зсуву, щоб вставити на потрібне місце 2. На весь процес нам було потрібно 2 + 2 + 1 = 5 зрушень.

На рис. 2.2 (b) ілюструється сортування Шелла. Ми починаємо, виробляючи сортування вставками з кроком 2. Спочатку ми розглядаємо числа 3 і 1: витягаємо 2, зрушуємо 3 на 1 позицію з кроком 2, вставляємо 2. Потім повторюємо те ж для чисел 5 і 2: витягаємо 2, зрушуємо вниз 5, вставляємо 2. І т.д. Закінчивши сортування з кроком 2, виробляємо її з кроком 1, тобто виконуємо звичайну сортування вставками. Всього при цьому нам знадобиться 1 + 1 + 1 = 3 зсуву. Таким чином, використавши спочатку крок, більший 1, ми домоглися меншого числа зрушень.

Мал. 2-2: Сортування Шелла

Можна використовувати найрізноманітніші схеми вибору кроків. Як правило, спочатку ми сортуємо масив з великим кроком, потім зменшуємо крок і повторюємо сортування. В самому кінці сортуємо з кроком 1. Хоча цей метод легко пояснити, його формальний аналіз досить важкий. Зокрема, теоретикам не вдалося знайти оптимальну схему вибору кроків. Кнут [1] провів безліч експериментів і знайшов наступну формулу вибору кроків h для масиву довжини N:

1 = 1, h s + 1 = 3 h s + 1, ... взяти h t, якщо h t + 2> = N.

Ось кілька перших значень h:

1 = 1
h 2 = (3 x 1) + 1 = 4
h 3 = (3 x 4) + 1 = 13
h 4 = (3 x 13) + 1 = 40
h 5 = (3 x 40) + 1 = 121

Щоб відсортувати масив довжиною 100, насамперед знайдемо номер s, для якого h s> = 100. Відповідно до наведених цифр, s = 5. Потрібне нам значення знаходиться двома рядками вище. Таким чином, послідовність кроків при сортуванні буде такою: 13-4-1. Ну, звичайно, нам не потрібно зберігати цю послідовність: чергове значення h знаходиться з попереднього за формулою

s-1 = [h s / 3].

Реалізація

В реалізації сортування Шелла на Сі слід змінити оператори typedef T і порівняння compGT так, щоб вони відповідали даним, збереженим в масиві. Основна частина алгоритму - сортування вставками з кроком h.