Рекомендуємо, 2024

Вибір Редакції

Різниця між сортуванням швидкого сортування та об'єднання

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

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

Діаграма порівняння

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

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

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

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

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

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

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

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

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

Нехай A - масив з n чисел елементів, які необхідно відсортувати A [1], A [2], ………, A [n]. За даними кроками виконується сортування.

  1. Розділіть масив A на приблизно n / 2 відсортованих підмасивів на 2, що означає, що елементи у (A [1], A [2]), (A [3], A [4]), (A [A] k], A [k + 1]), (A [n-1], A [n]) суб-масиви повинні бути в відсортованому порядку.
  2. Об'єднайте кожну пару пар, щоб отримати список відсортованих підматрив розміром 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]).
  3. Етап 2 неодноразово виконується до тих пір, поки не буде лише один сортований масив розміру n.

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

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

Ключові відмінності між сортуванням швидкого сортування та об'єднання

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

Висновок

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

Top