2. Сортування

2.1. Сортування вставками

Один із найпростіших способів відсортувати масив – сортування вставками. У звичайному житті ми стикаємося з цим методом під час гри в карти. Щоб відсортувати наявні у вас карти, ви виймаєте карту, зрушуєте карти, що залишилися, а потім вставляєте картку на потрібне місце. Процес повторюється доти, доки хоч одна карта знаходиться не на місці. Як середнє, і найгірший час цього алгоритму – O(n 2 ). Подальшу інформацію можна отримати у книзі Кнута [1].

На рис.2.2(a) ми виймаємо елемент 3. Потім елементи, розташовані вище, зрушуємо донизу, доки знайдемо місце, куди потрібно вставити 3. Цей процес триває на рис. 2.1(b) для числа 1. Нарешті, на рис.2.1(c) ми завершуємо сортування, помістивши 2 на потрібне місце.

Якщо довжина нашого масиву рівна n, нам потрібно пройтися по n – 1 елементам. Щоразу нам знадобиться зрушити n – 1 інших елементів. Ось чому цей метод вимагає досить багато часу.

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

Реалізація

Реалізацію сортування вставками на Сі ви знайдете у розділі 4.1. Операторtypedef Tі оператор порівнянняcompGTслід змінити так, щоб вони відповідали даним, що зберігаються в таблиці.

2.2. Сортування Шелла

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

На рис. 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. Хоча цей метод легко пояснити, його формальний аналіз досить важкий. Зокрема теоретикам не вдалося знайти оптимальну схему вибору кроків. Батіг[1] провів безліч експериментів і наступну формулу вибору кроків (h) для масиву довжини N:

у послідовності h1 = 1, hs + 1 = 3hs + 1. взяти ht, якщо ht + 2 і N.

Ось кілька перших значень h:h1= 1h2= (3 x 1) + 1 = 4h3= (3 x 4 ) + 1 = 13h4= (3 x 13) + 1 = 40h5= (3 x 40) + 1 = 121

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

Реалізація

Реалізацію сортування Шелла на Сі ви знайдете у розділі 4.2. Операторtypedef Tі оператор порівнянняcompGTслід змінити так, щоб вони відповідали даним, що зберігаються в масиві. Основна частина алгоритму – сортування вставками із кроком h.

2.3. Швидке сортування

Хоча ідея Шелла значно покращує сортування вставками, резерви ще залишаються. Один із найвідоміших алгоритмів сортування – швидке сортування, запропоноване Ч.Хоором. Метод і справді дуже швидкий, недарма англійською його так і називають QuickSort до невдоволення всіх спелл-чекерів (". Шишков пробач: не знаю, як перекласти").

Цьому методу потрібно O(n lg n) у середньому та O(n 2 ) у гіршому випадку. На щастя, якщо прийняти адекватні застереження, найгірший випадок є вкрай малоймовірним. Швидкий пошук не є стійким. З іншого боку, йому потрібно стек, тобто. він не є методом сортування на місці. Подальшу інформацію можна отримати у роботі Кормена [2].

Алгоритм розбиває масив, що сортується, на розділи, потім рекурсивно сортує кожен розділ. У функціїPartition(Рис. 2.3) один з елементів масиву вибирається як центральний. Ключі, меншіцентрального, слід розташувати зліва від нього, ті, які більше, - праворуч.

На рис. 2.4(a) як центральний вибраний елемент 3. Індекси починають змінюватися з кінців масиву.Індекс i починається зліва і використовується для вибору елементів, які більші за центральний, індекс j починається праворуч і використовується для вибору елементів, які менші за центральний. Ці елементи змінюються місцями – див. рис. 2.4(b). Процедура QuickSort рекурсивно сортує два підмасиви, в результаті виходить масив, представлений на рис. 2.4(с).

Як центральна функціяPartitionможе просто брати перший елемент (A[Lb]). Решта елементів масиву ми порівнюємо з центральним і пересуваємо або вліво від нього, або вправо. Є, однак, один випадок, який безжально руйнує цю чудову простоту. Припустимо, що наш масив від початку відсортований. ФункціяPartitionзавжди буде отримувати як центральний мінімальний елемент і тому розділить масив найгіршим способом: у лівому розділі виявиться один елемент, відповідно, у правому залишиться Ub – Lb елементів. Таким чином, кожен рекурсивний виклик процедури quicksort всього лише зменшить довжину масиву, що сортується на 1. В результаті для виконання сортування знадобиться n рекурсивних викликів, що призводить до часу роботи алгоритму порядку O(n 2 ). Один із способів подолати цю проблему – випадково обирати центральний елемент. Це зробить найгірший випадок надзвичайно малоймовірним.

Реалізація

Реалізація алгоритму Сі знаходиться в розділі 4.3. Операториtypedef TіcompGTслід змінити так, щоб вони відповідали даним, що зберігаються в масиві. Порівняно з основним алгоритмом є деякі покращення:

Як центральний у функціїpartitionвибирається елемент, розташований у середині. Такий вибір покращує оцінку середнього часу роботи, якщо масив упорядкований лише частково. Найгіршадля цієї реалізації ситуація виникає у разі, коли щоразу під час роботиpartition. Як центральний вибирається максимальний або мінімальний елемент.
Для коротких масивів викликається insertSort . Через рекурсію та інші “накладні витрати” швидкий пошук виявляється не таким вже швидким для коротких масивів. Тому, якщо масиві менше 12 елементів, викликається сортування вставками. Порогове значення не критично - воно сильно залежить від якості коду, що генерується.
Якщо останній оператор функції є викликом цієї функції, говорять про хвостову рекурсію. Її має сенс замінювати на ітерації – у цьому випадку краще використовується стек. Це зроблено за другого викликуQuickSortна рис. 2.3.
Після розбиття спочатку сортується менший розділ. Це також призводить до кращого використання стека, оскільки короткі розділи сортуються швидше і їм потрібен коротший стек.

У розділі 4.4 ви знайдете такожqsort– функцію зі стандартної бібліотеки Сі, яка, відповідно до назви, заснована на алгоритмі quicksort. Для цієї реалізації рекурсію замінили на ітерації. У таблиці 2.1 наводиться час і розмір стека, що витрачаються до та після описаних поліпшень.