O. (n2) Часова складність сортування вибору в найкращому випадку становить О. (n2). Середня складність регістру виникає, коли елементи масиву впорядковано в перемішаному порядку, який не є ні за зростанням, ні за спаданням правильно.
Часова складність алгоритмів сортування
| Назва алгоритму сортування | Найкраща складність часу | Найгірша складність часу |
|---|---|---|
| Швидке сортування | Ω(n log(n)) | O(n2) |
| Сортування вибору | Ω(n2) | O(n2) |
| Тім Сорт | Ω(n) | O(n log (n)) |
| Сортування купи | Ω(n log(n)) | O(n log(n)) |
Навіть якщо вхідні дані вже відсортовано, сортування за вибором все одно включає повторне сканування всіх несортованих елементів, щоб знайти наступний найменший. Отже, на відміну від сортування вставкою, воно залишатиметься O ( n 2 ) O(n^2) O(n2), навіть у найкращому випадку. Сортування вибору не покладається на жодні додаткові масиви, тому це O ( 1 ) O(1) O(1) пробіл.
Часова складність: Часова складність сортування вибору становить O(N2) оскільки є два вкладених цикли: один цикл для вибору елемента масиву один за одним = O(N) інший цикл для порівняння цього елемента з усіма іншими елементами масиву = O(N) Тому загальна складність = O(N) * O( N) = O(N*N) = O(N2)
Швидке сортування Швидке сортування це найшвидший відомий алгоритм сортування на основі порівняння при застосуванні до великих невпорядкованих послідовностей. Він також має перевагу сортування на місці (або майже на місці).