Зміст

• Порівняльна діаграма
• Визначення швидкого сортування
• Визначення сортування злиття
• Висновок

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

Обидві методи сортування, швидке сортування та сортування об'єднані на основі методу ділення та підкорення, в якому набір елементів розбиваються та об'єднуються після перестановки. Швидке сортування зазвичай вимагає більше порівнянь, ніж сортування для сортування великого набору елементів.

1. 1. Порівняльна діаграма
   2. Визначення
   3. Ключові відмінності
   4. Висновок

Порівняльна діаграма

Основа для порівняння	Швидке сортування	Злиття сортування
Розбиття елементів у масиві	Розщеплення списку елементів необов’язково ділиться навпіл.	Масив завжди розділений навпіл (n / 2).
Найгірша складність випадку	О (н.)2)	O (n журналу n)
Добре працює на	Менший масив	Добре працює в будь-якому типі масиву.
Швидкість	Швидше, ніж інші алгоритми сортування для невеликих наборів даних.	Постійна швидкість у всіх типах наборів даних.
Додаткова вимога місця для зберігання	Менше	Більше
Ефективність	Неефективний для великих масивів.	Більш ефективний.
Спосіб сортування	Внутрішня	Зовнішні

Визначення швидкого сортування

Швидке сортування широко розповсюджений алгоритм сортування, оскільки це швидко для коротких масивів. Набір елементів ділиться на частини неодноразово, поки його неможливо розділити далі. Швидкий сорт також відомий як сортування обміну розділами. Для розбиття елементів він використовує ключовий елемент (відомий як шарнір). Один розділ містить ті елементи, які менші за ключовий елемент. Інший розділ містить ті елементи, які перевищують ключовий елемент. Елементи сортуються рекурсивно.

Припустимо, A - це масив A, A, A, …… .., A з n числа, який необхідно сортувати. Алгоритм швидкого сортування складається з наступних етапів.

1. Перший елемент або будь-який випадковий елемент, обраний як ключ, припустимо ключ = A (1).
2. Вказівник “низький” розміщується на другому, а “вгору” вказівник розміщується на останньому елементі масиву, тобто низький = 2 та вгору = n;
3. Послідовно збільшуйте вказівник «низький» на одне положення до (A> клавіша).
4. Постійно декрементуйте покажчик «вгору» на одне положення до (A <= клавіша).
5. Якщо вгору більше, ніж низький, то взаємозамін A з А.
6. Повторіть крок 3,4 і 5, поки умова на кроці 5 не завершиться (тобто вгору <= низька), а потім обміняйте A з ключем.
7. Якщо елементів ліворуч від ключа менше ключа, а елементів праворуч від ключа більше ключа, то масив розподіляється на два підмасиви.
8. Вищеописана процедура неодноразово застосовується до підмагістралей, поки весь масив не буде відсортований.

   

   
   

Переваги і недоліки

Він має хорошу середню поведінку у випадку. Складність швидкого сортування в часі роботи - це швидше, ніж такі алгоритми, як сортування бульбашок, сортування вставки та сортування селекції. Однак він складний і дуже рекурсивний, тому він не підходить для великих масивів.

Визначення сортування злиття

Злиття сортування це зовнішній алгоритм, який також заснований на стратегії ділення та перемоги. Елементи розбиваються на підмасиви (n / 2) знову і знову, поки не залишиться лише один елемент, що значно скорочує час сортування. Він використовує додаткове сховище для зберігання допоміжного масиву. Сортування сортування використовує три масиви, де два використовуються для зберігання кожної половини, а третій використовується для зберігання остаточного відсортованого списку. Кожен масив потім сортується рекурсивно. Нарешті, підрядні масиви об'єднуються, щоб зробити його n розміром елемента масиву. Список завжди поділявся на лише половину (n / 2), відмінну від швидкого сортування.

Нехай A - це масив з n кількості елементів, які слід відсортувати A, A, ………, A. Сортування об'єднань відповідає наведеним крокам.

1. Розділити масив A приблизно на n / 2 відсортованому підмасиві на 2, що означає, що елементи в масивах (A, A), (A, A), (A, A), (A, A) повинні мати бути в упорядкованому порядку.
2. Об'єднайте кожну пару пар, щоб отримати список відсортованих підрисів розміром 4; елементи в підрисах також розташовуються в упорядкованому порядку (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Крок 2 повторно виконується, поки не буде лише один відсортований масив розміром n.

   

Переваги і недоліки

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

1. У сортуванні злиття масив повинен бути розділений на дві половини (тобто n / 2). На противагу, у швидкому роді, не існує примусу ділити список на рівні елементи.
2. Найгірша складність швидкого сортування - O (n²), оскільки це потребує набагато більше порівнянь у найгіршому стані. На відміну від цього, сортування злиття має однакові гірші випадки та середню складність випадку, тобто O (n log n).
3. Сортування сортування може добре працювати з будь-яким типом наборів даних, будь то великий чи малий. Навпаки, швидкий сорт не може добре працювати з великими наборами даних.
4. Швидке сортування швидше, ніж сортування злиття в деяких випадках, наприклад, для невеликих наборів даних.
5. Сортування сортування вимагає додаткового простору пам’яті для зберігання допоміжних масивів. З іншого боку, для швидкого сортування не потрібно багато місця для додаткового зберігання.
6. Сортування сортування є більш ефективним, ніж швидке сортування.
7. Швидке сортування - це метод внутрішнього сортування, коли дані, які потрібно сортувати, регулюються за один раз у основній пам'яті. І навпаки, сортування злиття - це метод зовнішнього сортування, при якому дані, які слід сортувати, не можуть одночасно розміщуватися в пам'яті, а деякі повинні зберігатися у допоміжній пам'яті.

Висновок

Швидке сортування - це більш швидкі випадки, але в деяких ситуаціях неефективне, а також виконує багато порівнянь порівняно з сортуванням злиття. Хоча сортування злиття вимагає меншого порівняння, для зберігання додаткового масиву потрібен додатковий простір пам'яті 0 (n), а для швидкого сортування потрібно простір O (log n).