Бульбашкове сортування включенням

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

Сортування впорядкованим бінарним деревом

Алгоритм складається з побудови впорядкованого бінарного дерева і подальшого його обходу. Якщо немає необхідності в побудові всього лінійного впорядкованого списку значень, то немає необхідності і в обході дерева, в цьому випадку застосовується пошук у впорядкованому бінарному дереві. Відзначимо, що порядок алгоритму – O(N*log2(N)), але в конкретних випадках все залежить від впорядкованості початкової послідовності, який впливає на ступінь збалансованості дерева і нарешті – на ефективність пошуку

Хоча обмінні алгоритми стратегії включення і дозволяють скоротити число порівнянь за наявності деякої початкової впорядкованості вхідної множини, значна кількість пересилок істотно знижує ефективність цих алгоритмів. Тому алгоритми включення доцільно застосовувати до зв’язних структур даних, коли операція перестановки елементів структури вимагає не пересилки даних в пам’яті, а виконується способом корекції покажчиків.

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

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

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

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