Алгоритми впорядкування списку. Обчислювальна та ємнісна складність алгоритму
Алгоритм сортування - це алгоритм для впорядкування елементів у списку. У випадку, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в інших полях зберігаються будь-які дані, ніяк що не впливають на роботу алгоритму.
Для типових алгоритмів в середньому обчислювальна складність O(n*log n), а в найгіршому – O(n2). Щодо пам'яті, то, зазвичай, необхідно O(log n) пам'яті.
Характеристики алгоритмів сортування:
– Стійкість– стійке сортування не змінює взаємного розташування елементів з однаковими ключами;
– Природність поведінки – ефективність методу при обробці вже впорядкованих або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
– Використання операції порівняння. Алгоритми, що використовують для сортування порівняння елементів між собою, називаються заснованими на порівняннях. Мінімальна трудомісткість гіршого випадку для цих алгоритмів становить O (n log n), але вони відрізняються гнучкістю застосування. Для спеціальних випадків (типів даних) існують більш ефективні алгоритми.
Алгоритм сортування вибіркою (Selection Sort)
Може бути як стійким, так і не стійким.
Кроки виконання алгоритму:
1) знаходимо номер мінімального значення в поточному списку;
2) проводимо обмін цього значення зі значенням першої невідсортованої позиції (обмін не потрібен, якщо мінімальний елемент вже знаходиться на даній позиції);
3) тепер сортуємо хвіст списку, виключивши з розгляду вже відсортовані елементи.
Для реалізації стійкості алгоритму необхідно в пункті 2 мінімальний елемент безпосередньо вставляти в першу невідсортовану позицію, не змінюючи порядок інших елементів.
Обчислювальна складність алгоритму: O(n2).
Ємнісна складність: O(1).
Алгоритм сортування бульбашкою (Bubble Sort)
Алгоритм працює таким чином — у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування за ним нагадує поведінку бульбашок повітря у резервуарі з водою.
Обчислювальна складність: O(n2).
Ємнісна складність: додаткових затрат пам'яті немає.
Алгоритм вставки або включення (Insertion Sort)
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку, до тих пір, поки набір вхідних даних не буде вичерпано. Метод вибору чергового елемента з вихідного масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються по порядку їх появи у вхідному масиві.
Обчислювальна складність алгоритму: O(n2)
Ємнісна складність: O(1).
Алгоритм швидкого сортування (Quick Sort)
Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.
Загальна ідея алгоритму полягає в наступному:
1) Вибрати з масиву елемент, званий опорним. Це може бути будь-який з елементів масиву.
2) Порівняти всі інші елементи з опорним і переставити їх у масиві так, щоб розбити масив на ldf безперервних відрізка, наступні один за одним - «менші опорного», «більші та рівні.
3) Для відрізків «менших» і «більших-рівних» значень виконати рекурсивно ту ж послідовність операцій, якщо довжина відрізка більше одиниці.
Складність алгоритму у найгіршому випадку – O(n2), в середньому і найкращому – O(n*log n).
Ємнісна складність: в залежності від реалізації може знадобитися до O(n) рекурсивних викликів, що може призвести до переповнення стеку.
Алгоритм злиття (Merge Sort)
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.
Обчислювальна складність: O(n*log n);
Ємнісна складність: O(n) додаткової пам'яті.
Алгоритм позиційного сортування (Radix Sort)
Це - швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). В якості допоміжного використовує будь-який інший стабільний алгоритм сортування.
Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен разряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті.
Складність алгоритму: O(D*(N+K)), де D – кількість розрядів, K – кількість символів алфавіту (10 – для цифр, 33 – для укр. алфавіту); для цілих чисел – O(N*log M), де M – найбільший елемент масиву.
Ємнісна складність: O(N+K).
Блокове сортування або сортування комірками (Bucket Sort)
Це стабільний алгоритм впорядкування, що доцільно використовувати, якщо вхідні дані розподілені рівномірно. В основі алгоритму лежить розподілення всіх елементів по скінченній кількості комірок. Кожна комірка впорядковується окремо іншим алгоритмом впорядкування або ж рекурсивно алгоритмом впорядкування комірками. Сортування комірками є узагальненням сортування підрахунком.
Переваги: відноситься до класу швидких алгоритмів з лінійним часом виконання O (N) (на вдалих вхідних даних).
Недоліки: сильно деградує при великій кількості мало відмінних елементів, або ж на невдалій функції отримання номера кошика по вмісту елементу.
Обчислювальна складність: O(n).
Ємнісна складність: створюється додатково масив зі списків, який буде різним в різних реалізаціях і залежатиму від ступеню діапазону даних.