Сортування розподілом.

Алгоритм порозрядного сортування вимагає представлення ключів сортованої послідовності у вигляді чисел в деякій системі числення P. Число проходів сортування рівно максимальному числу значущих цифр в числі – D. При кожному проході аналізується значуща цифра в черговому розряді ключа, починаючи з молодшого розряду. Всі ключі з однаковим значенням цієї цифри об’єднуються в одну групу. Ключі в групі розташовуються в порядку їхнього надходження. Після того, як вся початкова послідовність розподілена по групах, групи розташовуються в порядку зростання пов’язаних з групами цифр. Процес повторюється для другої цифри і т.д., поки не будуть вичерпані значущі цифри в ключі.

Алгоритм швидкого сортування Хоара відноситься до розподільних і забезпечує показники ефективності O(N*log2(N)) навіть при якнайгіршому початковому розподілі.

Використовується два індекси з початковими значеннями початку і кінця множини відповідно. Ключ початку порівнюється з ключем кінця. Якщо ключі задовольняють критерію впорядкованості, то індекс кінця зменшується на 1 і проводиться наступне порівняння. Якщо ключі не задовольняють критерію, то записи міняються місцями. При цьому індекс кінця фіксується і починає мінятися індекс початку (збільшуватися на 1 після кожного порівняння). Після наступної перестановки фіксується початок і починає змінюватися кінець і т.д. Прохід закінчується, коли індекси стають рівними. Запис, що знаходиться на позиції зустрічі індексів, стоїть на своєму місці в послідовності. Всі записи, розташовані ліворуч від неї мають ключі, менші ніж ключ цього запису, всі записи праворуч – більші. Той же самий алгоритм застосовується до лівої підмножини, а потім до правої. Записи підмножини розподіляються на дві менші підмножини і так далі. Розподіл закінчується, коли отримана підмножина буде складатися з єдиного елемента – така підмножина вже є впорядкованою.

Сортування злиттям.

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається— тоді решта іншої колони додається до нової.

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

Схема алгоритму для конкретного прикладу послідовності

Проілюструємо алгоритм сортування на такій послідовності: 42 5 30 36 25 10 37 49 0 0 На початку сортування відсортовані підпослідовності містять в собі по одному елементу.

Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0

Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0

Крок 3: 5 10 25 30 36 37 42 49 | 0 0

Крок 4: 0 0 5 10 25 30 36 37 42 49

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

1. Початкові установки. Визначити довжини першої і другої початкових множин – l1 і l2 відповідно. Встановити індекси поточних елементів в початковій множині і1 і і2 в 0. Встановити індекс в вихідній множині j=1.

2. Цикл злиття. Виконувати крок 3 до тих пір, поки і1<=l1 і і2<=l2.

3. Порівняння. Порівняти ключ і1-го елемента з першої початкової множини з ключем і2-го елемента з другої початкової множини. Якщо ключ елемента з 1-ої множини менший, то записати і1-тий елемент з 1-ої множини на j-те місце в вихідній множині і збільшити і1 на 1. Інакше – записати і2-тий елемент з 2-ої множини на j-те місце в вихідній множині і збільшити і2 на 1. Збільшити j на 1.

4. Виведення залишків. Якщо і1<=l1, то переписати частину 1-ої початкової множини від і1 до l1 включно в вихідну множину. Інакше – переписати частину 2-ої початкової множини від і2 до l2 включно в вихідну множину.