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

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

Складність алгоритму сортування бульбашкою: O(n²) на випадкових наборах даних.

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

Складність алгоритму сортування вибором: O(n²) на випадкових наборах даних.

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

Складність алгоритму швидкого сортування: O(n log n) у середньому випадку, O(n²) у найгіршому випадку.

Приклади сортування масивів довжиною 10000,20000,40000,80000 елементів.

Сортування бульбашкою. Bubble Sort:

Довжина масиву	Кількість обмінів	Час виконання

Сортування вибором. Selection sort.:

Довжина масиву	Кількість обмінів	Час виконання

Швидке сортування. Quick Sort:

Довжина масиву	Кількість обмінів	Час виконання