Размещено на http://www.allbest.ru/

105

Размещено на http://www.allbest.ru/

1. Побудова і аналіз алгоритміВ

1.1 Формалізація алгоритмів

алгоритм програмний пошук

Процес створення комп'ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів:

формалізація і створення технічного завдання на вихідну задачу;

розробка алгоритму вирішення задачі;

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

отримання розв'язку вихідної задачі шляхом виконання програми.

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

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

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

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

Є ще один аспект у визначення алгоритмів. Алгоритмічні інструкції повинні мати „чіткий зміст” і виконуватися з „скінченими обчислювальними затратами”. Природно, те, що зрозуміло одній людині і має для неї „чіткий зміст”, може зовсім інакше представлятися іншій. Те ж саме можна сказати про поняття „скінчених затрат”: на практиці часто важко довести, що при будь-яких вихідних даних виконання послідовності інструкцій завершиться, навіть якщо чітко розуміти зміст кожної інструкції. У цій ситуації, враховуючи всі аргументи за і проти, було б корисним спробувати досягнути узгодження про „скінченні затрати” у відношенні до послідовності інструкцій, які складають алгоритм.

1.2 Покрокове проектування алгоритмів

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

В основу процесу проектування програми з розбиттям її на достатню кількість дрібних кроків можна покласти наступну послідовність дій:

1. Вихідним станом процесу проектування є більш-менш точне формулювання мети алгоритму, або конкретніше - результату, який повинен бути отриманий при його виконанні. Формулювання проводиться на природній мові.

2. Проводиться збір фактів, які стосуються будь-яких характеристик алгоритму, і робиться спроба їх представлення засобами мови.

3. Створюється образна модель процесу, який відбувається, використовуються графічні та інші способи представлення, образні „картинки”, які дозволяють краще зрозуміти виконання алгоритму в динаміці.

4. В образній моделі виділяється найбільш суттєва частина, для якої підбирається найбільш точне словесне формулювання.

5. Проводиться визначення змінних, які необхідні для формального представлення даного кроку алгоритму.

6. Вибирається одна з конструкцій - проста послідовність дій, умовна конструкція або циклу. Складні частини вибраної формальної конструкції (умова, заголовок циклу) залишаються в словесному формулюванні.

7. Для інших неформалізованих частин алгоритму, які залишились у словесному формулюванні - перерахована послідовність дій повторюється.

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

Схематично узагальнений процес програмування можна представити наступною схемою.

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

На наступному етапі алгоритм записується на псевдомові - композиції конструкцій мови програмування і менш формальних і узагальнених операторів на простій мові. Продовженням цього етапу є заміна неформальних операторів послідовністю більш детальних і формальних операторів. З цієї точки зору програма на псевдомові повинна бути достатньо детальною, так як в ній фіксуються (визначаються) різні типи даних, над якими виконуються оператори. Потім створюються абстрактні типи даних для кожного зафіксованого типу даних (за винятком елементарних типів даних, таких як цілі й дійсні числа або символьні стрічки) шляхом завдання імен функцій для кожного оператора, який працює з даними абстрактного типа, і заміни їх (операторів) викликом відповідних функцій.

Третій етап процесу - програмування - забезпечує реалізацію кожного абстрактного типа даних і створення функцій для виконання різних операторів над даними цих типів. На цьому етапі також замінюються всі неформальні оператори псевдомови на код мови програмування. Результатом цього етапу повинна бути виконувана програма. Після її наладки отримують працюючу програму.

1.3 Характеристики алгоритму

Охарактеризуємо поняття алгоритму не формально, а дескриптивно за допомогою таблиці:

	Вирішення гарантоване
	Так	Ні
Чи обов'язкове оптимальне вирішення	Так	Алгоритм	Імовірнісний алгоритм
	Ні	Приблизний алгоритм	Евристичний алгоритм

Як бачимо, алгоритм - це механізм, який не тільки повинен гарантувати те, що вирішення колись буде знайдене, але й те, що буде знайдене саме оптимальне, тобто найкраще вирішення. Крім того, алгоритм повинен мати наступні п'ять якостей:

1. Обмеженість в часі - робота алгоритму обов'язково повинна завершитись через деякий розумний період часу.

2. Правильність - алгоритм повинен знаходити правильне, а не будь-яке рішення.

3. Детермінованість - скільки б разів не виконувався алгоритм з однаковими вхідними даними, результат повинен бути однаковим.

4. Скінченність - опис роботи алгоритму повинен мати скінчену кількість кроків.

5. Однозначність - кожний крок алгоритму повинен інтерпретуватися однозначно.

Як видно з таблиці, евристика - це пряма протилежність класичному алгоритму, так як вона не дає ніяких гарантій на те, що рішення буде знайдене, так само, як і на те, що воно буде оптимальним. Між ними є два перехідні стани, назв яким, на жаль, ще не придумали, і тому їх називають приблизними алгоритмами (рішення гарантоване, але його оптимальність - ні) і імовірнісні алгоритми (рішення не гарантоване, але якщо воно буде знайдене, то обов'язково буде оптимальним).

1.4 Складність алгоритму

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

1. Бути простим для розуміння, перекладу в програмний код і наладки.

2. Ефективно використовувати комп'ютерні ресурси і виконуватися швидко.

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

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

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

Більшість алгоритмів надає вибір між швидкістю виконання і ресурсами. Задача може виконуватися швидше, використовуючи більше пам'яті, або навпаки - повільніше з меншим обсягом пам'яті.

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

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

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

1.5 Ефективність алгоритмів

Одним із способів визначення часової ефективності алгоритмів полягає в наступному: на основі даного алгоритму потрібно написати програму і виміряти час її виконання на певному комп'ютері для вибраної множини вхідних даних. Хоча такий спосіб популярний і, безумовно, корисний, він породжує певні проблеми. Визначений час виконання програми залежить не тільки від використаного алгоритму, але й від архітектури і набору внутрішніх команд даного комп'ютера, від якості компілятора, і від рівня програміста, який реалізував даний алгоритм. Час виконання також може суттєво залежати від вибраної множини тестових вхідних даних. Ця залежність стає очевидною при реалізації одного й того ж алгоритму з використанням різних комп'ютерів, різних компіляторів, при залучені програмістів різного рівня і при використанні різних тестових даних. Щоб підвищити об'єктивність оцінки алгоритмів, учені, які працюють в галузі комп'ютерних наук, прийняли асимптотичну часову складність як основну міру ефективності виконання алгоритму.

Часто говорять, що час виконання алгоритму має порядок T(N) від вхідних даних розміру N. Одиниця вимірювання T(N) точно не визначена, але в більшості випадків розуміють під нею кількість інструкцій, які виконуються на ідеалізованому комп'ютері.

Для багатьох програм час виконання дійсно є функцією вхідних даних, а не їх розміру. У цьому випадку визначають T(N) як час виконання в найгіршому випадку, тобто, як максимум часів виконання за всіма вхідними даними розміру N. Поряд з тим розглядають T_ср(N) як середній (в статистичному розумінні) час виконання за всіма вхідними даними розміру N. Хоча T_ср(N) є достатньо об'єктивною мірою виконання, але часто неможливо передбачити, або обґрунтувати, рівнозначність усіх вхідних даних. На практиці середній час виконання знайти складніше, ніж найгірший час виконання, так як математично це зробити важко і, крім цього, часто не буває простого визначення поняття „середніх” вхідних даних. Тому, в основному, користуються найгіршим часом виконання як міра часової складності алгоритмів.

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

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

Функція	Примітка
f(N)=C	C - константа
f(N)=log(log(N))
f(N)=log(N)
f(N)=NC	C - константа від нуля до одиниці
f(N)=N
f(N)=N*log(N)
f(N)=NC	C - константа більша одиниці
f(N)=CN	C - константа більша одиниці
f(N)=N!	тобто 1*2* … N

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

У числових алгоритмах точність і стійкість алгоритмів не менш важлива, ніж їх часова ефективність.

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

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

1.6 Правила аналізу складності алгоритмів

У загальному випадку час виконання оператора або групи операторів можна розглядати як функцію з параметрами - розміром вхідних даних і/або одної чи декількох змінних. Але для часу виконання програми в цілому допустимим параметром може бути лише розмір вхідних даних.

Час виконання операторів присвоєння, читання і запису звичайно має порядок .

Час виконання послідовності операторів визначається за правилом сум. Тому міра росту часу виконання послідовності операторів без визначення констант пропорційності співпадає з найбільшим часом виконання оператора в даній послідовності.

Час виконання умовних операторів складається з часу виконання умовно виконуваних операторів і часу обчислення самого логічного виразу. Час обчислення логічного виразу часто має порядок . Час для всієї конструкції if-then-else складається з часу обчислення логічного виразу і найбільшого з часів, який необхідний для виконання операторів, що виконуються при різних значеннях логічного виразу.

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

2. Алгоритми сортування

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

При подальших викладках всі описи алгоритмів дані для роботи з таблицею, яка складається із записів R[0], ..., R[N-1] з ключами K[0], ..., K[N-1]. У всіх випадках N - кількість елементів таблиці. Приклади для скорочення їхнього обсягу приводитимемо для масивів цілих чисел. Такий масив можна розглядати як вироджений випадок таблиці, кожний запис якої складається з єдиного поля, яке є також і ключем. У всіх прикладах слід вважати вже визначеними:

константу N - ціле додатне число, кількість елементів в масиві;

масив цілих чисел, над яким проводять зазначені дії.

2.1 Задача сортування

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

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

1. Наявний ресурс пам'яті: повинні вхідна й вихід множини розташовуватися в різних ділянках пам'яті, чи вихідна множина може бути сформована на місці вхідної. В останньому випадку наявна ділянка пам'яті повинна в ході сортування динамічно перерозподілятися між вхідною і вихідною множинами; для одних алгоритмів це пов'язане з великими витратами, для інших - з меншими.

2. Початкова впорядкованість вхідної множини: у вхідній множині можуть попадатися впорядковані ділянки. В граничному випадку вхідна множина може виявитися вже впорядкованою. Одні алгоритми не враховують початкової впорядкованості і вимагають одного і того ж часу для сортування будь-якої множини даного обсягу, інші виконуються тим швидше, чим краще впорядкованість на вході.

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

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

Алгоритм сортування називається усталеним, якщо у відсортованому масиві він не змінює порядку розташування елементів.

Ефективність методів сортування визначається двома параметрами:

кількістю порівнянь;

кількістю пересилань елементів.

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

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

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

3. Стратегія розподілу. Вхідна множина розбивається на ряд підмножин і сортування ведеться у середині кожної такої підмножини.

4. Стратегія злиття. Вихідна множина отримується шляхом злиття маленьких впорядкованих підмножин.

При використанні операції обміну використовується функція обміну значень двох комірок з цілими числами (функції пересилки даних можна уникнути, якщо сортування проводиться на зв'язних структурах даних - тоді відбувається зміна посилань на відповідні комірки):

void Swap(int & a, int & b)

{

int tmp = a; a = b; b = tmp;

}

2.2 Сортування вибіркою

2.2.1 Сортування простою вибіркою

Даний метод реалізує практично „дослівно” сформульовану вище стратегію вибірки. При програмній реалізації алгоритму виникає проблема значення ключа „порожньо”. Досить часто програмісти використовують в якості такого деяке явно відсутнє у вхідній послідовності значення ключа, наприклад, максимальне з теоретично можливих значень. Інший підхід - створення окремого вектора, кожний елемент якого має логічний тип і відображає стан відповідного елемента вхідної множини (true - „не порожньо”, false - „порожньо”). Алгоритм дещо ускладнюється за рахунок того, що для установки початкового значення при пошуку мінімуму доводиться відкидати вже „порожні” елементи.

Алгоритм проілюструємо функцією сортування цілих чисел.

void Sort(int *a, int *b)

{

int i, j, m;

bool c[N]; // стан елементів вхідної множини

for (i=0; i<N; i++)

c[i] = true; // скидання відміток

for (i=0; i<N; i++) // пошук 1-го невибраного ел. у вх. множині

{

j = 0;

while ( !(c[j]) )

j++;

m = j; // пошук мінімального елемент а

for ( j=1; j<N; j++ )

if ( c[j] && ( a[j] < a[m] ) )

m = j;

b[i] = a[m]; // запис у вихід. множину

c[m] = false; // у вхідну множину - "порожньо"

}

}

2.2.2 Обмінне сортування простою вибіркою

Алгоритм сортування простою вибіркою рідко застосовується в попередньому варіанті. Набагато частіше застосовується його обмінний варіант. При обмінному сортуванні вибіркою вхідна і вихід множини розташовуються в одній і тій же ділянці пам'яті; вихідна - на початку ділянки, вхідна - в тій частині, що залишилася. У початковому стані вхідна множина займає всю ділянку, а вихідна множина - порожня. У міру виконання сортування вхідна множина звужується, а вихідна - розширяється.

Принцип методу полягає в наступному. Знаходять і вибирають в масиві елементів елемент з мінімальним значенням на інтервалі від 0 (першого) до N-1 (останнього) елемента і міняють його місцями з першим (0) елементом. На другому кроці знаходять елемент з мінімальним значенням на інтервалі від другого (1) до останнього (N-1) елемента і міняють місцями його з другим (1) елементом. І так далі для всіх елементів до N-1.

Обмінне сортування простою вибіркою показане в наступному прикладі. Процедура має тільки один параметр - сортований масив.

void Sort(int *a)

{

int i, j, m;

for (i=0; i<N-1; i++) // перебір елементів вихідної множини

// вхідна множина - [і:N-1]; вихідна - [0:і-1]

{

m = i;

for (j=i+1; j<N; j++) // пошук мінімуму у вхідній множині

if ( a[j] < a[m] )

m = j;

// обмін 1-го елемента вх. множини з мінімальним

if ( !(i == m) )

Swap(a[i], a[m]);

}

}

Очевидно, що обмінний варіант забезпечує економію пам'яті та при його реалізації не виникає проблема „порожнього” значення. Загальна кількість порівнянь зменшується удвічі - N*(N-1)/2, але порядок алгоритму залишається степеневим - . Кількість перестановок N-1, але перестановка, мабуть, удвічі більше потребує часу, ніж пересилка в попередньому алгоритмі.

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

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

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

При перегляді вхідної множини попарно порівнюються сусідні елементи множини. Якщо порядок їхнього проходження не відповідає заданому критерію впорядкованості, то елементи міняються місцями. В результаті одного такого перегляду при сортуванні за збільшенням елементів елемент з найбільшим значенням ключа переміститься („спливе”) на останнє місце в множині. При наступному проході на своє місце „спливе” другий за величиною ключа елемент і т.д. Для постановки на свої місця N елементів слід зробити N-1 проходів. Вихідна множина, таким чином, формується в кінці сортованої послідовності, при кожному наступному проході його об'єм збільшується на 1, а об'єм вхідної множини зменшується на 1.

void Sort(int *a)

{

int k, i;

for ( k=N; k>1; k-- )

// „Всплиття” чергового максимального елемента на k-ту позицію

for ( i=1; i<k; i++ )

if ( a[i-1] > a[i] )

Swap(a[i-1], a[i]);

}

Порядок сортування бульбашкою - . Середнє число порівнянь - N*(N-1)/2 і таке ж середнє число перестановок, що значно гірше, ніж для обмінного сортування простим вибором. Проте, та обставина, що тут завжди порівнюються і переміщаються тільки сусідні елементи, робить сортування бульбашкою зручним для обробки зв'язних списків. Перестановка в зв'язних списках також виходить більш економною.

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

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

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

void Sort(int *a)

{

int nn, i, x;

nn = N; // межа вхідної множини

do

{

x = 0; // ознака перестановок

for ( i=1; i<nn; i++ ) // перебір вхідної множини

if ( a[i-1] > a[i] ) // порівняння сусідніх елементів

{

Swap(a[i-1], a[i]); // перестановка

x = i; // запам'ятовування позиції

}

nn = x; // зсув межі

}

while (nn>0); // цикл поки вих. множина не захопить весь масив

}

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

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

Це ще одна модифікація сортування бульбашкою. Суть її полягає в тому, що тут виконується порівняння ключів, віддалених один від одного на деяку відстань d. Початковий розмір d звичайно вибирається рівним половині загального розміру сортованої послідовності. Виконується сортування бульбашкою з інтервалом порівняння d. Потім величина d зменшується удвічі і знов виконується сортування бульбашкою, далі d зменшується ще удвічі і т.д. Останнє сортування бульбашкою виконується при d=1. Якісний порядок сортування Шелла залишається , середнє ж число порівнянь, визначене емпіричним шляхом, - N*log2(N)^2. Прискорення досягається за рахунок того, що виявленні „не на місці” елементи при d>1, швидше „спливають” на свої місця. Наступний приклад ілюструє сортування Шелла.

void Sort(int *a)

{

int d, i, t;

bool k; // ознака перестановки

d = N / 2; // початкове значення інтервалу

while (d>0) // цикл із зменшенням інтервалу до 1

{

k = true; // сортування бульбашкою з інтервалом d

while (k) // цикл, поки є перестановки

{

k = false;

for ( i=0; i<N-d; i++ )// порівняння ел-тів на інтервалі d

if ( a[i] > a[i+d] )

{

Swap(a[i], a[i+d]); // перестановка

k = true; // ознака перестановки

};

};

d = d / 2;// зменшення інтервалу

};

}

2.3 Сортування включенням

2.3.1 Сортування простим включенням

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

Алгоритм сортування простим включенням ілюструється прикладом.

void Sort(int *a, int *b)

{

int i, j, k;

for ( i=0; i<N; i++ ) // перебір вхідного масиву

{

// пошук місця для в масиві виходу

j = 0;

while ((j<i) && (b[j]<=a[i]))

j++;

// звільнення місця для нового ел-та

for ( k=i; k>j; k-- )

b[k] = b[k-1];

b[j] = a[i];// запис в масив виходу

};

}

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

Реалізація алгоритму обмінного сортування простими вставками відрізняється від базового алгоритму тільки тим, що вхідна і вихідна множина розміщені в одній ділянці пам'яті.

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

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

void Sort (int *a)

{

int i, j, k, t;

for ( i=1; i<N; i++ ) // перебір вхідного масиву

{

// *** вх.множина - [і..N-1], вих.множина - [0..і]

t = a[i]; // запам'ятовується значення нового ел-та

j = i-1; //пошук місця для ел-та у вих. множині з зсувом

// цикл закінчиться досягши початку або,

// коли зустріне ел-т, менший нового

while ((j >= 0) && (a[j]>t))

a[j+1] = a[j--]; // всі ел-ти, більші нового зсовуються

// цикл від кінця до початку множини виходу

a[j+1] = t; // новий ел-т ставиться на своє місце

};

}

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

2.3.3 Турнірне сортування

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

Наприклад, для послідовності чисел:

16 21 8 14 26 94 30 1

таке дерево буде мати вид піраміди:

У наступному прикладі приведена програмна ілюстрація цього алгоритму. Побудова піраміди виконується функцією CreateHeap. Піраміда будується від основи до вершини. Елементи, що становлять кожний рівень, зв'язуються в лінійний список, тому кожний вузол дерева крім звичайних покажчиків на нащадків - left і right - містить і покажчик на „брата” - next. При роботі з кожним рівнем покажчик містить початкову адресу списку елементів в даному рівні. На першій фазі будується лінійний список для нижнього рівня піраміди, в елементи якого заносяться ключі з початкової послідовності. Наступний цикл while в кожній своїй ітерації надбудовує наступний рівень піраміди. Умовою завершення цього циклу є отримання списку, що складається з єдиного елемента, тобто, вершини піраміди. Побудова чергового рівня полягає в попарному переборі елементів списку, що становить попередній (нижній) рівень. На новий рівень переноситься якнайменше значення ключа з кожної пари.

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

Функція HeapSort одержує вхідний параметр ph - покажчик на вершину піраміди, і формує вихідний параметр - впорядкований масив чисел. Уся функція HeapSort складається з циклу, в кожній ітерації якого значення з вершини переноситься в масив, а потім викликається функція Competit, яка забезпечує реорганізацію піраміди у зв'язку з видаленням значення з вершини.

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

// Турнірне сортування

struct node // вузол дерева

{

int key; // дані

node *left;

node *right; // покажчики на нащадків

node *next; // покажчик на "брата"

};

// Створення дерева

// функція повертає покажчик на вершину створеного дерева

node* HeapCreate(int *a)

{

int i;

node *ph2; // адреса початку списку рівня

node *p1; // адреса нового елемента

node *p2; // адреса попереднього елемента

node *pp1;

node *pp2; // адреси пари, що змагається

// Фаза 1 - побудова самого нижнього рівня піраміди

ph2 = NULL;

for ( i=0; i<N; i++ )

{

p1 = new node; // виділення пам'яті для нового ел-та

p1->key = a[i]; // запис даних з масиву

p1->left = NULL;

p1->right = NULL; // нащадків немає

// зв'язування в лінійний список по рівню

if ( ph2 == NULL )

ph2 = p1;

else

p2->next = p1;

p2 = p1;

}

p1->next = NULL;

// Фаза 2 - побудова інших рівнів

while (!(ph2->next == NULL)) // цикл до вершини піраміди

{

pp1 = ph2;

ph2 = NULL; // початок нового рівня

while (!(pp1 == NULL)) // цикл по черговому рівню

{

pp2 = pp1->next;

p1 = new node;

// адреси нащадків з попереднього рівня

p1->left = pp1;

p1->right = pp2;

p1->next = NULL;

// зв'язування в лінійний список по рівню

if ( ph2 == NULL )

ph2 = p1;

else

p2->next = p1;

p2 = p1;

// змагання даних за вихід на рівень

if ( (pp2 == NULL) || (pp2->key > pp1->key) )

p1->key = pp1->key;

else

p1->key = pp2->key;

// перехід до наступної пари

if ( !(pp2 == NULL) )

pp1 = pp2->next;

else

pp1 = NULL;

}

}

return ph2;

}

// Реорганізація поддерева

// функція повертає покажчик на вершину реорганизованного дерева

node* Competit(node *ph)

{

// визначення наявності нащадків,

// вибір нащадка для реорганізації,

// реорганізація його

if ( !(ph->left == NULL) && (ph->left->key==ph->key) )

ph->left = Competit(ph->left);

else if ( !(ph->right == NULL) )

ph->right = Competit(ph->right);

if ( (ph->left == NULL) && (ph->right==NULL) )

{

// звільнення порожнього вузла

delete ph;

ph = NULL;

}

else

// змагання даних нащадків

if ( (ph->left == NULL) ||

( !(ph->right == NULL) && (ph->left->key > ph->right->key) ) )

ph->key = ph->right->key;

else

ph->key = ph->left->key;

return ph;

}

// Сортування

void HeapSort(int *a)

{

node * ph; // адреса вершини дерева

int i;

ph = HeapCreate(a); // створення дерева

// вибірка з дерева

for ( i=0; i<N; i++ )

{

// перенесення даних з вершини в масив

A[i] = ph->key;

// реорганізація дерева

ph = Competit(ph);

}

}

Побудова дерева вимагає N-1 порівнянь, вибірка - N*log2(N) порівнянь. Порядок алгоритму, таким чином, - O(N*log2(N)). Складність операцій над зв'язними структурами даних, проте, значно вища, ніж над статичними структурами. Крім того, алгоритм неекономний відносно пам'яті: дублювання даних на різних рівнях піраміди приводить до того, що робоча ділянка пам'яті містить приблизно 2*N вузлів.

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

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

Заслуговує на увагу модифікація цього алгоритму запропонована Р.Флойдом. Метод сортування за допомогою прямої вибірки базується на повторних пошуках найменшого ключа серед n елементів, серед тих що залишилися n-1 елементів і так далі. Виявлення найменшого серед n елементів потребує - n-1 порівнянь, серед n-1 вже потрібно n-2 порівнянь і так далі. Як же в такому випадку можна удосконалити згаданий метод сортування? Цього можна добитися, тільки залишаючи після кожного проходу більше інформації, ніж просто ідентифікація єдиного мінімального елемента. Наприклад, виконавши n/2 порівнянь, можна визначити в кожній парі ключів менший. За допомогою n/4 порівнянь - менший із пари вже вибраних менших і так далі. Провівши n-1 порівнянь, можна побудувати дерево вибору і ідентифікувати його корінь як потрібний найменший ключ.

Другий етап сортування - спуск вздовж шляху, відміченого найменшим елементом, і виключення його з дерева шляхом заміни або на пустий елемент (дірку) в самому низу, або на елемент із сусідньої гілки в проміжних вершинах. Елемент, який перемістився в корінь дерева, знову буде найменшим (тепер вже другим) ключем, і його можна виключити. Після n таких кроків дерево стане пустим і процес сортування завершується.

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

Р. Флойдом був запропонований деякий „лаконічний” спосіб побудови піраміди „на тому ж місці”, який використовує функцію зсуву елементів початкового вектора:

int a[N];

void shift(L, R)

{

i=L;

j=2*L;

x=a[L];

if ( (j<=L) && (a[j]<a[j+1]) )

j++;

while ( (j<=R) && (x<a[j]) )

{

a[i] = a[j];

i = j;

j = 2*j;

if (j<R) && (a[j]<a[j+1])

j++;

}

}

void Sort(void)

{

L=1+N*0.5;

R=N;

while (L>1)

{

L--;

shift(L, R)

}

while (R>1)

{

x = a[1];

a[1] = a[R];

a[R] = x;

R--;

sift(L, R)

}

}

2.3.5 Сортування частково впорядкованим деревом

У бінарному дереві, яке будується в цьому методі сортування для кожного вузла справедливе наступне твердження: значення ключа, записане у вузлі, менше, ніж ключі його нащадків. Для повністю впорядкованого дерева є вимоги до співвідношення між ключами нащадків. Для даного дерева таких вимог немає, тому таке дерево і називається частково впорядкованим. Крім того, таке дерево повинно бути абсолютно збалансованим. Це означає не тільки те, що довжини шляхів до будь-якого двох листків розрізняються не більш, ніж на 1, але і те, що при додаванні нового елемента в дерево перевага завжди віддається лівій гілці, поки це не порушує збалансованість.

Представлення дерева у вигляді піраміди наочно показує, що для такого дерева можна ввести поняття „початку” і „кінця”. Початком, природно, буде вважатися вершина піраміди, а кінцем - самий крайній лівий елемент.

Для сортування цим методом потрібно визначити дві операції: вставка в дерево нового елемента і вибірка з дерева мінімального елемента; причому виконання будь-якій з цих операцій не повинне порушувати ні сформульованої вище часткової впорядкованості дерева, ні його збалансованості.

Алгоритм вставки полягає в наступному. Новий елемент вставляється на перше вільне місце за кінцем дерева. Якщо ключ вставленого елемента менший, ніж ключ його предка, то предок і вставлений елемент міняються місцями. Ключ вставленого елемента тепер порівнюється з ключем його предка на новому місці і так далі. Порівняння закінчуються, коли ключ нового елемента виявиться більшим ключа предка або коли новий елемент „випливе” у вершину піраміди.

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

Впорядкованість дерева відновлена, але порушено умову його збалансованості, оскільки вільне місце знаходиться не в кінці дерева. Для відновлення збалансованості останній елемент дерева переноситься на місце, що звільнилося, а потім „спливає” по тому ж алгоритму, який застосовувався при вставці.

Перш, ніж описувати приклад, що ілюструє сортування частково впорядкованим деревом, потрібно звернути увагу на спосіб, яким в ньому дерево представлене в пам'яті. Це спосіб представлення бінарних дерев в статичній пам'яті, який може бути застосований і в інших задачах. Елементи дерева розташовуються в сусідніх комірках пам'яті за рівнями. Найперша комірка виділеної пам'яті займає вершина. Наступні дві комірки - елементи другого рівня, наступні 4 - третього і т.д.

При такому представленні відпадає необхідність зберігати у складі вузла дерева покажчики, оскільки адреси нащадків можуть бути обчислені. Для вузла, представленого елементом масиву з індексом і індекси його лівого і правого нащадків будуть 2*і+1 і 2*і+2, відповідно. Для вузла з індексом і індекс його предка буде (і-1)/2.

Після всього вищесказаного алгоритм прикладу не потребує особливих пояснень. Пояснимо тільки структуру прикладу. Саме дерево представлене в масиві tree, змінна nt є індексом першого вільного елемента в масиві. Функції для роботи:

функція InitST - ініціалізація модуля, установка початкового значення nt;

функція InsertST - вставка в дерево нового елемента; функція повертає false, якщо в дереві немає вільного місця, інакше - true;

функція DeleteST - вибірка з дерева мінімального елемента; функція повертає false, якщо дерево порожнє, інакше - true;

функція Down - забезпечує спуск вільного місця з вершини піраміди в її основу, функція повертає індекс вільного місця після спуску;

функція Up - забезпечує спливання елемента із заданого місця.

// Сортування частково впорядкованим деревом

int tr[N]; // дерево

int nt; // індекс останнього елемента в дереві

// Спливання елемента з місця з індексом l

void Up(int l)

{

int h; // l - індекс вузла, h - індекс його предка

h = ( l - 1 ) / 2; // індекс предка

while ( h >= 0 ) // до початку дерева

{

if (tr[l] < tr[h])

{

// ключ вузла менше, ніж в предка

Swap(tr[l], tr[h]); // перестановка

l = h;

h = ( l - 1 ) / 2; // предок стає поточним вузлом

}

else

h = -1; // кінець спливання

}

}

// Спуск вільного місця з початку дерева

int Down(void)

{

int h, l; // h - індекс вузла, l - індекс його нащадка

h = 0; // початковий вузол - початок дерева

while (true)

{

l = h * 2 + 1; // обчислення індексу 1-го нащадка

if ( l+1 <= nt )

{

// у вузла є 2-й нащадок

if ( tr[l] <= tr[l+1] )

{

// 1-й нащадок менше 2-го

tr[h] = tr[l]; // 1-й нащадок переноситься в поточний вузол

h = l; // 1-й нащадок стає поточним вузлом

}

else

{

// 2-й нащадок менше 1-го

tr[h] = tr[l+1]; // 2-й нащадок переноситься в поточний вузол

h = l + 1; // 2-й нащадок стає поточним вузлом

}

}

else

if ( l == nt )

{

// 1-й нащадок є, 2-го немає

tr[h] = tr[l]; // 1-й нащадок переноситься в поточний вузол

return l; // спуск закінчений

}

else

// нащадків немає - спуск закінчений

return h;

}

}

// Ініціалізація сортування деревом

void InitST(void)

{

nt = -1; // дерево порожнє

}

// Вставка eл-та в дерево

bool InsertST(int a)

{

if ( nt == N-1)

return false; // дерево заповнене - відмова

else // в дереві є місце

{

tr[++nt] = a; // запис в кінець дерева

Up(nt); // спливання

return true;

}

}

// Вибірка eлемента з дерева

bool DeleteST(int & a)

{

int n;

if ( nt == -1 ) // дерево порожнє - відмова

return false;

else // дерево не порожнє

{

a = tr[0]; // вибірка eл-та з початку

n = Down(); // спуск вільного місця в позицію n

if ( n < nt )

{

// якщо вільне місце спустилося не в кінець дерева

tr[n] = tr[nt]; // eл-т з кінця переноситься на вільне місце

Up(n); // спливання

}

nt = nt-1;

return true;

}

}

Якщо застосовувати сортування частково впорядкованим деревом для впорядкування вже готової послідовності розміром N, то необхідно N раз виконати вставку, а потім N раз - вибірку. Порядок алгоритму - O(N*log2(N)), але середнє значення кількості порівнянь приблизно в 3 рази більше, ніж для турнірного сортування. Але сортування частково впорядкованим деревом має одну істотну перевагу перед всіма іншими алгоритмами - це найзручніший алгоритм для „сортування on-line”, коли сортована послідовність не зафіксована до початку сортування, а міняється в процесі роботи і вставки чергують з вибірками. Кожна зміна (додавання елемента) сортованої послідовності вимагає тут не більш, ніж 2*log2(N) порівнянь і перестановок, в той час, як інші алгоритми вимагають при одиничній зміні нового впорядковування всієї послідовності „за повною програмою”.

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

2.4.1 Порозрядне цифрове сортування

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