Разлика между сортиране за бързо сортиране и сливане

• 2019

Алгоритмите за бързо сортиране и сливане се основават на алгоритъма divide and conquer, който работи по доста сходен начин. Предварителната разлика между бързото и сливане е, че в бързото сортиране се използва въртящият елемент за сортиране. От друга страна, сортирането на сливане не използва опорен елемент за извършване на сортирането.

И двете техники за сортиране, бърз сортиране и сливане са построени на метода на разделяне и завладяване, при който наборът от елементи е разделен и след това комбиниран след прегрупиране. Бързото сортиране обикновено изисква повече сравнения, отколкото сортирането за сливане на голям набор от елементи.

Сравнителна таблица

Основа за сравнение	Бързо сортиране	Обединяване сортиране
Разделяне на елементите в масива	Разделянето на списък от елементи не е задължително разделено на половината.	Масивът винаги се разделя на половина (n / 2).
Най-лошата сложност на случая	О (N2)	O (n log n)
Работи добре	По-малък масив	Работи добре във всеки тип масив.
скорост	По-бързи от другите алгоритми за сортиране за малък набор от данни.	Постоянна скорост във всички типове данни.
Изисква се допълнително място за съхранение	По-малко	| Повече ▼
Ефективност	Неефективно за по-големи масиви.	По-ефикасно.
Метод на сортиране	вътрешен	Външен

Дефиниция на бързо сортиране

Бързото сортиране е широко използван алгоритъм за сортиране, тъй като е бърз за късите масиви. Наборът от елементи се разделя на части многократно, докато не е възможно да се раздели допълнително. Бързото сортиране също е известно като сортиране на дялове . Той използва ключов елемент (известен като pivot) за разделяне на елементите. Един дял съдържа онези елементи, които са по-малки от ключовия елемент. Друг дял съдържа онези елементи, които са по-големи от ключовия елемент. Елементите се сортират рекурсивно.

Да предположим, че А е масив A [1], A [2], A [3], ……, A [n] от n номер, които трябва да бъдат сортирани. Алгоритъмът за бърз сортиране се състои от следните стъпки.

1. Първият елемент или произволен елемент, избран като ключ, предполага ключ = A (1).
2. “Ниският” показалец се поставя на втория и “нагоре” указателят се позиционира в последния елемент на масива, т.е. нисък = 2 и нагоре = n;
3. Последователно увеличавайте „ниската” стрелка с една позиция, докато (A [ниска]> клавиша).
4. Постоянно намалявайте стрелката нагоре с една позиция, докато (A [нагоре] <= клавиш).
5. Ако е по-голям от нисък обмен A [ниско] с A [нагоре].
6. Повторете стъпка 3, 4 и 5, докато условието в стъпка 5 се провали (т.е. до <= ниско), след което разменяте A [нагоре] с бутона.
7. Ако елементите вляво от ключа са по-малки от ключа и елементите отдясно на ключа са по-големи от ключа, масивът е разделен на две под-масиви.
8. Горната процедура се прилага многократно към подраздели, докато целият масив се сортира.

Предимства и недостатъци

Той притежава добро средно поведение на делата. Времевата сложност на бързото сортиране е добра, че е по-бърза от алгоритми като сортиране на балон, сортиране на вмъкване и подбор. Въпреки това, той е сложен и много рекурсивен, поради което не е подходящ за големи масиви.

Дефиниция на сортиране на сливане

Сливането е външен алгоритъм, който също се основава на стратегия за разделяне и завладяване. Елементите се разделят на под-масиви (n / 2) отново и отново, докато остане само един елемент, което значително намалява времето за сортиране. Той използва допълнително място за съхранение на помощния масив. Merge sort използва три масива, където две се използват за съхраняване на всяка половина, а третият се използва за съхраняване на окончателния сортиран списък. След това всеки масив се сортира рекурсивно. Най-сетне, подраздели се обединяват, за да се получи n размер на елемента на масива. Списъкът винаги се разделя на само половината (n / 2), различни от бързите.

Нека A е масивът от n брой елементи, които трябва да бъдат сортирани A [1], A [2], ………, A [n]. Сливането следва следните стъпки.

1. Разделете масива А на приблизително n / 2 подредени под масив с 2, което означава, че елементите в (А [1], А [2]), (А [3], А [4]), (А [ 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).