Både sorteringstekniker, snabb sortering och sammanslagning är byggda på delningen och erövra metoden där uppsättningen av elementen delas och sedan kombineras efter omarrangemang. Den snabba sorteringen kräver vanligtvis mer jämförelser än att slå samman för att sortera en stor uppsättning element.
Jämförelsediagram
| Grunder för jämförelse | Snabb sortering | Merge sort |
|---|---|---|
| Partitionering av elementen i matrisen | Uppdelningen av en lista med element är inte nödvändigtvis uppdelad i hälften. | Array är alltid uppdelad i hälften (n / 2). |
| Värsta fall komplexitet | O (n2) | O (n log n) |
| Fungerar bra | Mindre utbud | Fungerar bra i någon typ av array. |
| Fart | Snabbare än andra sorteringsalgoritmer för små dataset. | Konsekvent hastighet i alla typer av dataset. |
| Ytterligare krav på lagringsutrymme | Mindre | Mer |
| Effektivitet | Ineffektiv för större arrays. | Mer effektiv. |
| Sorteringsmetod | Inre | Extern |
Definition av snabb sortering
Snabb sortering är allmänt använd sorteringsalgoritm eftersom det är snabbt för de korta arraysna. Satsen av elementen är uppdelad i delar upprepade gånger tills det inte går att dela upp det ytterligare. Snabb sortering är också känd som partitionsbytes sortering . Det använder ett nyckelelement (kallat pivot) för partitionering av elementen. En partition innehåller de element som är mindre än nyckelelementet. En annan partition innehåller de element som är större än nyckelelementet. Elementen sorteras rekursivt.
Antag att A är en grupp A [1], A [2], A [3], ...... .., A [n] av n-nummer som måste sorteras. Snabbsorteringsalgoritmen bestod av följande steg.
- Det första elementet eller något slumpmässigt element som valts som nyckeln, antar nyckeln = A (1).
- Den "låga" pekaren placeras vid den andra och "upp" -pekaren är placerad vid det sista elementet i matrisen, dvs låg = 2 och upp = n;
- Stig konsekvent upp den "låga" pekaren med ett läge tills (A [låg]> -tangenten).
- Ständigt minskar "upp" pekaren med en position tills (A [upp] <= tangent).
- Om upp är större än låg utbyte A [låg] med A [upp].
- Upprepa steg 3, 4 och 5 tills tillståndet i steg 5 misslyckas (dvs upp <= lågt) och byt ut A [upp] med nyckeln.
- Om elementen som lämnas av nyckeln är mindre än nyckeln och elementen till höger om nyckeln är större än nyckeln är uppdelningen uppdelad i två delrader.
- Ovanstående procedur appliceras upprepade gånger på subarrayerna tills hela sortimentet är sorterat.
Fördelar och nackdelar
Den har ett bra genomsnittligt fallbeteende. Körtidskomplexiteten i den snabba sorteringen är bra, eftersom den är snabbare än algoritmer som sortering av bubblar, inmatningssort och urvalssortering. Det är emellertid komplext och mycket rekursivt, det är anledningen till att det inte är lämpligt för stora arrays.
Definition av sammanslagningssort
Merge sort är en extern algoritm som också är baserad på dela och erövra strategi. Elementen delas upp i delraderingar (n / 2) om och om igen tills endast ett element lämnas vilket avsevärt minskar sorteringstiden. Det använder extra lagringsutrymme för lagring av hjälpmatrisen. Sammanfoga sorterar använder tre arrays där två används för att lagra varje halva, och den tredje används för att lagra den slutliga sorterade listan. Varje array sorteras därefter rekursivt. Äntligen slås subarrayerna samman för att göra det n elementstorleken av matrisen. Listan är alltid uppdelad i bara hälften (n / 2) olik till snabb sortering.
Låt A vara arrayen av n antal element som ska sorteras A [1], A [2], ........., A [n]. Sammanslagningssorten följer de angivna stegen.
- Dela upp array A i ungefär n / 2 sorterad undergrupp med 2, vilket innebär att elementen i A [1], A [2], A [3], A [4]), A [ k], A [k + 1]), (A [n-1], A [n]) delrader måste vara i sorterad ordning.
- Kombinera varje parpar för att få en lista över sorterade subarrays av storlek 4; elementen i subarrayerna är också i sorterade ordning, (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]).
- Steget 2 utförs upprepade gånger tills det bara finns en sorterad array med storlek n.
Fördelar och nackdelar
Sammanslagningsalgoritmen utför på exakt samma och exakta sätt oavsett antal element som är inblandade i sorteringen. Det fungerar bra även med den stora datasatsen. Men det förbrukar större del av minnet.
Viktiga skillnader mellan Quick Sorter och Merge Sorter
- I sammanslagningssorten måste uppdelningen delas in i bara två halvor (dvs n / 2). I motsats till, i snabb sortering, är det ingen tvång att dela upp listan i lika delar.
- Det svåraste komplexet av snabb sort är O (n2) eftersom det tar mycket mer jämförelser i värsta skick. I motsats härtill har sammanslagningssort samma värsta fall och medeltalskomplexiteter, det vill säga O (n log n).
- Sammanfoga sortera kan fungera bra på alla typer av dataset om det är stort eller litet. Tvärtom kan den snabba sorteringen inte fungera bra med stora dataset.
- Snabb sortering är snabbare än sammanslagning i vissa fall, t.ex. för små dataset.
- Sammanfoga sorterar kräver extra minnesutrymme för att lagra hjälpskivorna. Å andra sidan kräver snabb sorten inte mycket utrymme för extra lagring.
- Sammanslagning är effektivare än snabb sortering.
- Snabb sortering är intern sorteringsmetod där data som ska sorteras justeras åt gången i huvudminnet. Omvänt är sammanslagningssorten extern sorteringsmetod där de data som ska sorteras inte kan tillgodoses i minnet samtidigt och vissa måste behållas i extraminne.
Slutsats
Den snabba sorteringen är snabbare fall men är ineffektiv i vissa situationer och utför också mycket jämförelser jämfört med sammanslagningssort. Även om sammanslagningssort kräver mindre jämförelse behöver den ett extra minnesutrymme på 0 (n) för att lagra den extra matrisen, medan snabb sortering behöver plats för O (log n).
