Технике сортирања, сортирање брзих сорти и спајања су изграђене на методи поделе и освајања, при чему се скуп елемената раздваја и затим комбинира након преуређивања. Брзо сортирање обично захтева више поређења него сортирање за сортирање великог скупа елемената.
Цомпарисон Цхарт
| Основа за поређење | Брзо сортирање | Сортирање спајањем |
|---|---|---|
| Раздвајање елемената у низу | Раздвајање листе елемената није нужно подељено на пола. | Арраи се увек дели на пола (н / 2). |
| Најгора сложеност случаја | О (н2) | О (н лог н) |
| Добро ради | Мањи низ | Добро функционише у било којој врсти поља. |
| Брзина | Бржи од других алгоритама сортирања за мали скуп података. | Уједначена брзина у свим типовима података. |
| Потребан додатни простор за складиштење | Мање | Више |
| Ефикасност | Неефикасно за веће низове. | Ефикаснији. |
| Метод сортирања | Интерно | Ектернал |
Дефиниција брзог сортирања
Брзо сортирање је распрострањено кориштен алгоритам сортирања, јер је брз за кратке низове. Скуп елемената је више пута подељен на делове док га није могуће даље поделити. Брзо сортирање је такође познато као сортирање партиција . Она користи кључни елемент (познат као пивот) за партиционисање елемената. Једна партиција садржи оне елементе који су мањи од кључног елемента. Друга партиција садржи оне елементе који су већи од кључног елемента. Елементи се сортирају рекурзивно.
Претпоставимо да је А низ А [1], А [2], А [3], ……, А [н] од н броја који треба сортирати. Брзи алгоритам сортирања састоји се од сљедећих корака.
- Први елемент или било који насумични елемент изабран као кључ, претпоставља кључ = А (1).
- "Ниски" показивач је постављен на други, а "горе" показивач је позициониран на последњи елемент низа, тј. Низак = 2 и горе = н;
- Доследно повећавајте „ниски“ показивач за једну позицију док (А [ниска]> тастер).
- Непрекидно смањујте “уп” показивач за једну позицију све док (А [горе] <= тастер).
- Ако је горе већи од ниског размјене А [ниско] са А [горе].
- Поновите кораке 3, 4 и 5 све док се стање у кораку 5 не поквари (тј. До <= ниско), а затим промените А [горе] са тастером.
- Ако су елементи лево од кључа мањи од кључа, а елементи десно од кључа су већи од кључа, онда је низ подељен на два под-поља.
- Горе наведена процедура се вишекратно примењује на подарраје све док се не сортира цео низ.
Предности и мане
Има добро просечно понашање. Сложеност брзог покретања брзе сорте је добра јер је бржа од алгоритама као што су сортирање балона, сортирање уметања и сортирање. Међутим, он је сложен и врло рекурзиван, због чега није погодан за велике низове.
Дефиниција сортирања спајања
Сортирање спајања је спољни алгоритам који се такође заснива на стратегији поделе и осваја. Елементи су подељени у под-низове (н / 2) поново и поново све док не остане само један елемент, што значајно смањује време сортирања. Користи додатну меморију за чување помоћног низа. Мерге сорт користи три поља у којима се два користе за спремање сваке половине, а трећи се користи за спремање коначне сортиране листе. Сваки низ се затим сортира рекурзивно. Напокон, субарраис се спајају да би се направило н величине елемента низа. Листа је увек подељена на само половину (н / 2) различиту од брзе сорте.
Нека је А низ од н бројева елемената које треба сортирати А [1], А [2], ………, А [н]. Сортирање спајања прати задане кораке.
- Раздвојите низ А у приближно н / 2 сортираних под-поља за 2, што значи да елементи у (А [1], А [2]), (А [3], А [4]), (А [ к], А [к + 1]), (А [н-1], А [н]) под-поља морају бити у сортираном реду.
- Комбинујте сваки пар парова да бисте добили листу сортираних подарара величине 4; елементи у субарраис су такође у сортираном реду, (А [1], А [2], А [3], А [4], ……, (А [к-1], А [к], А [к + 1], А [к + 2]), ……., (А [н-3], А [н-2], А [н-1], А [н]).
- Корак 2 се понавља све док не постоји само један сортирани низ величине н.
Предности и мане
Алгоритам за сортирање спајања изводи се на исти и прецизан начин без обзира на број елемената укључених у сортирање. Добро ради и са великим скупом података. Међутим, он троши већи део меморије.
Кључне разлике између сортирања брзог сортирања и спајања
- Код сортирања спајања, поље мора бити раздвојено на само две половине (тј. Н / 2). Насупрот томе, у брзом смислу, нема присиле да се листа подели на једнаке елементе.
- Најгори случај сложености брзог сортирања је О (н2) јер је потребно много више поређења у најгорем стању. Насупрот томе, сорта спајања има исту најгору и просјечну сложеност случаја, то јест О (н лог н).
- Сортирање спајања може добро функционирати на било којој врсти скупова података било да је велика или мала. Напротив, брза сорта не може добро радити са великим скуповима података.
- Брзо сортирање је брже од сортирања спајања у неким случајевима, као код малих скупова података.
- Сортирање спајања захтева додатни меморијски простор за складиштење помоћних поља. С друге стране, брза сорта не захтева много простора за додатно складиштење.
- Сортирање спајања је ефикасније од брзе сортирања.
- Брзо сортирање је интерни метод сортирања у којем се подаци који се сортирају прилагођавају истовремено у главној меморији. Насупрот томе, сортирање је спољни метод сортирања у којем се подаци који се сортирају не могу истовремено смјестити у меморију, а неки се морају чувати у помоћној меморији.
Закључак
Брзо сортирање је бржи случај, али је у неким ситуацијама неефикасно и такође обавља много поређења у поређењу са сортирањем. Иако сортирање спајања захтева мање поређења, потребно му је додатно меморијско место од 0 (н) за чување додатног низа, док брзо сортирање захтева простор О (лог н).
