Разлика между Бързо сортиране и Сливане Сортиране
Съдържание
Бързото сортиране и обединяване на алгоритмите за сортиране се основават на алгоритъма разделяне и завладяване, който работи по доста подобен начин. Предходната разлика между сортирането за бързо и сливане е, че при бързото сортиране шарнирният елемент се използва за сортирането. От друга страна, сортирането на сливане не използва въртящ елемент за извършване на сортирането.
И двете техники за сортиране, бързото сортиране и сортирането се основават на метода на разделяне и завладяване, при който наборът от елементи се разделя и след това се комбинира след пренареждане. Бързото сортиране обикновено изисква повече сравнения, отколкото сортиране за сортиране на голям набор от елементи.
-
- Сравнителна диаграма
- дефиниция
- Ключови разлики
- заключение
Сравнителна диаграма
| Основа за сравнение | Бързо сортиране | Обединяване сортиране |
|---|---|---|
| Разделяне на елементите в масива | Разделянето на списък от елементи не е непременно разделено на половина. | Масивът винаги е разделен на половина (n / 2). |
| Най-лошата сложност на случая | О (п2) | O (n log n) |
| Работи добре на | По-малък масив | Работи добре във всеки тип масив. |
| скорост | По-бързи от другите алгоритми за сортиране на малки набори от данни. | Постоянна скорост във всички видове набори от данни. |
| Допълнително изискване за място за съхранение | По-малко | | Повече ▼ |
| Ефективност | Неефективен за по-големи масиви. | По-ефикасно. |
| Метод за сортиране | вътрешен | Външен |
Определение за Бързо сортиране
Бързо сортиране се използва широко разпространен алгоритъм за сортиране, тъй като е бърз за късите масиви. Наборът от елементи се разделя на части многократно, докато не е възможно да се раздели допълнително. Бързият сорт също е известен като сортиране на дялове, Той използва ключов елемент (известен като въртене) за разделяне на елементите. Един дял съдържа онези елементи, които са по-малки от ключовия елемент. Друг дял съдържа онези елементи, които са по-големи от ключовия елемент. Елементите са сортирани рекурсивно.
Да предположим, че A е масив A, A, A, …… .., A от n номер, който трябва да бъде сортиран. Алгоритъмът за бързо сортиране се състои от следните стъпки.
- Първият елемент или който и да е случаен елемент, избран като ключ, приемете ключ = A (1).
- „Ниският“ показалец се поставя на втория, а „нагоре“ показалецът се позиционира в последния елемент от масива, т.е. нисък = 2 и нагоре = n;
- Последователно увеличавайте ниския показалец с една позиция до (A> бутон).
- Постоянно декрементирайте показалеца "нагоре" от една позиция до (A <= клавиш).
- Ако нагоре е по-голям от нисък обмен А с А.
- Повтаряйте стъпка 3,4 и 5, докато състоянието в стъпка 5 не се провали (т.е. нагоре <= ниско), след което обменяйте А с ключа.
- Ако елементите отляво на ключа са по-малки от ключа, а елементите отдясно на ключа са по-големи от ключа, тогава масивът е разделен на два подмасива.
- Горната процедура многократно се прилага към подредовете, докато се сортира целият масив.
Предимства и недостатъци
Притежава добро средно поведение в случая. Сложността на бързото сортиране на времето на работа е добра, че е по-бърза от алгоритми като сортиране на балончета, сортиране на вмъкване и сортиране на селекция. Той обаче е сложен и много рекурсивен, това е причината да не е подходящ за големи масиви.
Определение за сортиране на сливане
Обединяване сортиране е външен алгоритъм, който също се основава на стратегия за разделяне и завладяване. Елементите се разделят на подмасиви (n / 2) отново и отново, докато остане само един елемент, което значително намалява времето за сортиране. Той използва допълнително хранилище за съхранение на помощния масив. Сливането сортиране използва три масива, където два се използват за съхранение на всяка половина, а третият се използва за съхраняване на окончателния сортиран списък. След това всеки масив се сортира рекурсивно. Най-накрая подредовете се обединяват, за да направят n елемент на масива. Списъкът винаги е разделен на само половината (n / 2), различни от бързо сортиране.
Нека A е масив от n брой елементи, които трябва да бъдат сортирани A, A, ………, A. Сортирането на следи следва дадените стъпки.
- Разделете масива A на приблизително n / 2 сортиран под-масив по 2, което означава, че елементите в под-масивите (A, A), (A, A), (A, A), (A, A) трябва да да бъде в подреден ред.
- Комбинирайте всяка двойка двойки, за да получите списъка с подредени подредове с размер 4; елементите в подредовете също са в подреден ред, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
- Стъпка 2 се изпълнява многократно, докато има само един сортиран масив с размер n.
Предимства и недостатъци
Алгоритъмът за сортиране на сливане изпълнява по абсолютно същия и прецизен начин, независимо от броя на елементите, включени в сортирането. Работи добре дори и с големия набор от данни. Той обаче консумира по-голяма част от паметта.
- При сортирането на сливане масивът трябва да бъде разделен на само две половини (т.е. n / 2). За разлика от това, в бърз вид, няма принуда да се раздели списъка на равни елементи.
- Най-лошият случай на сложност на бързото сортиране е O (n2), тъй като отнема много повече сравнения в най-лошо състояние. За разлика от сортирането на сливане имат еднакви най-лоши и средни сложни случаи, тоест O (n log n).
- Сливането може да работи добре на всеки тип набори от данни, независимо дали е голям или малък. Напротив, бързото сортиране не може да работи добре с големи набори от данни.
- Бързото сортиране е по-бързо, отколкото сортирането в някои случаи, като например за малки набори от данни.
- Сливането сортиране изисква допълнително пространство в паметта за съхранение на помощните масиви. От друга страна, бързото сортиране не изисква много място за допълнително съхранение.
- Сливането сортиране е по-ефективно от бързо сортиране.
- Бързото сортиране е метод за вътрешно сортиране, при който данните, които трябва да бъдат сортирани, се настройват наведнъж в основната памет. Обратно, сортирането на сливане е метод за външно сортиране, при който данните, които трябва да бъдат сортирани, не могат да бъдат поместени в паметта едновременно, а някои трябва да се съхраняват в спомагателната памет.
заключение
Бързото сортиране е по-бързи случаи, но е неефективно в някои ситуации и също така извършва много сравнения в сравнение с сортирането на сливане. Въпреки че сортирането на сливане изисква по-малко сравнение, то се нуждае от допълнително пространство в паметта 0 (n) за съхранение на допълнителния масив, докато бързото сортиране се нуждае от пространство на O (log n).
