Сортування вибором.
Порівняння загальних характеристик роботи різних методів сортування
Загальний аналіз ефективності «швидкої» сортування досить важкий. Буде краще показати її обчислювальну складність, підрахувавши число порівнянь при деяких ідеальних припущеннях. Припустимо, що n — ступінь двійки, n = 2k (k = log2n), а центральний елемент розташовується точно посередині кожного списку і розбиває його на два підсписки приблизно однакової довжини. Якщо масив відсортований… Читати ще >
Сортування вибором. Порівняння загальних характеристик роботи різних методів сортування (реферат, курсова, диплом, контрольна)
Оцінимо часову складність даного методу, використовуючи в якості основної операції операцію порівняння.
Для пошуку мінімального елемента в кожному проході потрібно виконати: n-1, n-2, 1 операцій порівняння, тобто всього n (n-1) / 2 операцій порівняння. Отже, обчислювальна складність даного методу O (n2). Причому час сортування не залежить від вихідного порядку елементів.
Рисунок 3.2 — Алгоритм сортування вибором.
Метод швидкого сортування
Загальний аналіз ефективності «швидкої» сортування досить важкий. Буде краще показати її обчислювальну складність, підрахувавши число порівнянь при деяких ідеальних припущеннях. Припустимо, що n — ступінь двійки, n = 2k (k = log2n), а центральний елемент розташовується точно посередині кожного списку і розбиває його на два підсписки приблизно однакової довжини.
При першому скануванні проводиться n-1 порівнянь. В результаті створюються два підсписки розміром n / 2. На наступній фазі обробка кожного підсписки вимагає приблизно n / 2 порівнянь. Загальне число порівнянь на цій фазі дорівнює 2 (n / 2) = n. На наступній фазі обробляються чотири підсписки, що вимагає 4 (n / 4) порівнянь, і т.д. Зрештою процес розбиття припиняється після k проходів, коли вийшли підсписки містять по одному елементу. Загальне число порівнянь приблизно дорівнює n + 2 (n / 2) + 4 (n / 4) + … + N (n / n) = n + n + … + N = n * k = n * log2n.
Для списку загального вигляду обчислювальна складність «швидкої» сортування дорівнює O (n log2 n). Ідеальний випадок, який ми тільки що розглянули, фактично виникає тоді, коли масив вже відсортований за зростанням. Тоді центральний елемент потрапляє точно в середину кожного підсписки.
Якщо масив відсортований за спаданням, то на першому проході центральний елемент виявляється на середині списку і змінюється місцями з кожним елементом як у першому, так і в другому підсписки. Результуючий список майже відсортований, алгоритм має складність порядку O (n log2n).(рис. 3.2.1).
«Рисунок 3.2.1?опис методу швидкого сортування».
Найгіршим сценарієм для «швидкої» сортування буде той, при якому центральний елемент весь час потрапляє в одноелементні подспісок, а всі інші елементи залишаються в другому підсписки. Це відбувається тоді, коли центральним завжди є найменший елемент. Розглянемо послідовність 3, 8, 1, 5, 9.
На першому проході проводиться n порівнянь, а більший подспісок містить n-1 елементів. На наступному проході цей подспісок вимагає n-1 порівнянь і дає подспісок з n-2 елементів і т.д. Загальне число порівнянь одно: n + n-1 + n-2 + … + 2 = n (n +1) / 2 — 1.
Складність найгіршого випадку дорівнює O (n2), тобто не краще, ніж для сортувань вставками і вибором. Однак цей випадок є патологічним і малоймовірний на практиці. Загалом, середня продуктивність «швидкої» сортування вище, ніж у всіх розглянутих нами сортувань.
Алгоритм QuickSort вибирається за основу в більшості універсальних сортують утиліт. Якщо ви не можете змиритися з продуктивністю найгіршого випадку, використовуйте пірамідальну сортування — більш стійкий алгоритм, складність якого дорівнює O (n log2n) і залежить тільки від розміру списку.
Метод сортування бульбашкою
Алгоритм метод бульбашки — найбільш простий метод сортування масиву. Через своєї простоти цей метод не дуже ефективний і вимагає процесорного часу більше, ніж інші методи. Однак для сортування невеликих масивів використання методу бульбашки прийнятно. Припустимо, що масив сортується в порядку зростання, тоді метод бульбашки використовує цикл за значеннями масиву, переміщаючи поступово найбільше значення в кінець масиву (подібно до того, як в воді спливає на поверхню пляшечку).
Сортування методом бульбашки займає 61,3 секунд.