Обидві методи сортування, сортування швидкого сортування та злиття побудовані на методі divide і conquer, в якому набір елементів розділяється і потім об'єднується після перегрупування. Для сортування великого набору елементів для швидкого сортування зазвичай потрібно більше порівнянь, ніж сортування злиття.
Діаграма порівняння
| Основа для порівняння | Швидкий сортування | Об'єднати сортування |
|---|---|---|
| Розбиття елементів в масиві | Розбиття списку елементів не обов'язково ділиться на половину. | Масив завжди ділиться на половину (n / 2). |
| Найгірший випадок складності | O (n2) | O (n log n) |
| Добре працює | Менший масив | Відмінно працює в будь-якому типі масиву. |
| Швидкість | Швидше, ніж інші алгоритми сортування для малого набору даних. | Послідовна швидкість у всіх типах наборів даних. |
| Необхідність додаткового місця для зберігання | Менше | Більше |
| Ефективність | Неефективно для великих масивів. | Більш ефективний. |
| Метод сортування | Внутрішній | Зовнішній |
Визначення швидкого сортування
Швидкий сортування широко використовують алгоритм сортування, оскільки він є швидким для коротких масивів. Безліч елементів розділяється на частини багато разів, поки не можна розділити його далі. Швидкий сортування також відомий як сортування обміну розділами . Він використовує ключовий елемент (відомий як pivot) для розбиття елементів. Один розділ містить ті елементи, які є меншими за ключовий елемент. Інший розділ містить ті елементи, які більше, ніж ключовий елемент. Елементи сортуються рекурсивно.
Припустимо, що A - це масив A [1], A [2], A [3], ……, A [n] з n номерів, які повинні бути відсортовані. Алгоритм швидкого сортування складається з наступних кроків.
- Перший елемент або будь-який випадковий елемент, вибраний в якості ключа, передбачає ключ = A (1).
- Вказівник «низький» розміщується на другому, а вказівник «вгору» позиціонується на останній елемент масиву, тобто низький = 2 і up = n;
- Послідовно збільшуйте покажчик «низький» на одну позицію, доки (A [низька]> клавіша).
- Постійно зменшуйте вказівник "вгору" на одну позицію, поки (A [up] <= key).
- Якщо вище, ніж низький обмін A [низький] з A [вгору].
- Повторіть крок 3, 4 і 5, доки не станеться умова на кроці 5 (тобто до <= низького), потім обміняєте A [вгору] з ключем.
- Якщо елементи ліворуч від клавіші менше, ніж ключ, а елементи праворуч від ключа більше, ніж ключ, то масив розділяється на два суб-масиви.
- Наведена вище процедура неодноразово застосовується до підполя, поки не буде відсортовано весь масив.
Переваги і недоліки
Вона має хорошу середню поведінку справи. Складна робота швидкого сортування хороша тим, що вона швидше, ніж алгоритми, такі як сортування міхура, сортування вставки та сортування. Проте, він складний і дуже рекурсивний, тому він не підходить для великих масивів.
Визначення сортування злиття
Сортування злиття - це зовнішній алгоритм, який також базується на стратегії поділу та перемоги. Елементи розбиваються на суб-масиви (n / 2) знову і знову, поки не залишиться тільки один елемент, що значно зменшує час сортування. Він використовує додаткове сховище для зберігання допоміжного масиву. У режимі злиття використовуються три масиви, де два використовуються для зберігання кожної половини, а третій використовується для зберігання остаточного сортованого списку. Потім кожен масив сортується рекурсивно. Нарешті, піддіапазони об'єднуються, щоб зробити його n елементом розміру масиву. Список завжди ділиться лише на половину (n / 2), що відрізняється від швидкого сортування.
Нехай A - масив з n чисел елементів, які необхідно відсортувати A [1], A [2], ………, A [n]. За даними кроками виконується сортування.
- Розділіть масив A на приблизно n / 2 відсортованих підмасивів на 2, що означає, що елементи у (A [1], A [2]), (A [3], A [4]), (A [A] k], A [k + 1]), (A [n-1], A [n]) суб-масиви повинні бути в відсортованому порядку.
- Об'єднайте кожну пару пар, щоб отримати список відсортованих підматрив розміром 4; елементи в подмассивах також впорядковані, (A [1], A [2], A [3], A [4], ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- Етап 2 неодноразово виконується до тих пір, поки не буде лише один сортований масив розміру n.
Переваги і недоліки
Алгоритм сортування злиття виконується точно та точно, незалежно від кількості елементів, що беруть участь у сортуванні. Він працює відмінно навіть з великим набором даних. Однак вона споживає більшу частину пам'яті.
Ключові відмінності між сортуванням швидкого сортування та об'єднання
- У сортуванні злиття масив необхідно розділити на дві половинки (тобто n / 2). На відміну від цього, у швидкому порядку немає примусу поділу списку на рівні елементи.
- Найгірший випадок складності швидкого сортування - це O (n2), оскільки це займає набагато більше порівнянь у найгіршому стані. Навпаки, сортування злиття мають однаковий найгірший випадок і середній випадок складності, тобто O (n log n).
- Злиття сортування може працювати добре на будь-якому типі наборів даних, незалежно від того, чи є він великим або малим. Навпаки, швидкий сортування не може добре працювати з великими наборами даних.
- Швидкий сортування в деяких випадках швидше, ніж сортування злиття, наприклад, для малих наборів даних.
- Сортування злиття вимагає додаткового простору пам'яті для зберігання допоміжних масивів. З іншого боку, швидкий сортування не вимагає багато місця для додаткового зберігання.
- Сортування злиття є більш ефективним, ніж швидке сортування.
- Метод швидкого сортування - це внутрішній метод сортування, в якому дані, які потрібно відсортувати, налаштовуються одночасно в основній пам'яті. І навпаки, сортування злиття є зовнішнім методом сортування, при якому дані, які потрібно відсортувати, не можуть бути розміщені в пам'яті одночасно, а деякі повинні зберігатися в допоміжній пам'яті.
Висновок
Швидкий сортування відбувається швидше, але неефективно в деяких ситуаціях, а також виконує багато порівнянь порівняно з сортуванням об'єднань. Хоча сортування злиття вимагає меншого порівняння, для зберігання додаткового масиву потрібен додатковий простір пам'яті 0 (n), а для швидкого сортування потрібно простір O (log n).
