Både sorteringsteknikker, hurtig sortering og sammenslåing sorteres på divisjonen og erobre metoden der settet av elementer deles og deretter kombineres etter omplassering. Den raske sorteringen krever vanligvis mer sammenligninger enn å slå sammen for å sortere et stort sett med elementer.
Sammenligningstabel
| Grunnlag for sammenligning | Rask sortering | Merge sort |
|---|---|---|
| Partisjonering av elementene i matrisen | Oppdelingen av en liste over elementer er ikke nødvendigvis delt inn i halvparten. | Array er alltid delt inn i halvparten (n / 2). |
| Verste tilfelle kompleksitet | O (n2) | O (n log n) |
| Fungerer godt | Mindre matrise | Fungerer bra i enhver type matrise. |
| Hastighet | Raskere enn andre sorteringsalgoritmer for små datasett. | Konsekvent hastighet i alle typer datasett. |
| Ekstra lagringsplass krav | Mindre | Mer |
| Effektivitet | Ineffektiv for større arrays. | Mer effektivt. |
| Sorteringsmetode | Innvendig | Utvendig |
Definisjon av rask sortering
Hurtig sortering er pervasivt brukt sorteringsalgoritme som det er raskt for de korte arrays. Settet av elementene er delt inn i deler gjentatte ganger inntil det ikke er mulig å dele det videre. Hurtig sortering er også kjent som partisjonsutvekslings sortering . Den bruker et nøkkelelement (kjent som pivot) for partisjonering av elementene. En partisjon inneholder de elementene som er mindre enn nøkkelelementet. En annen partisjon inneholder de elementene som er større enn nøkkelelementet. Elementene er sortert rekursivt.
Anta at A er en gruppe A [1], A [2], A [3], ...... .., A [n] av n nummer som må sorteres. Den raske sorteringsalgoritmen består av de følgende trinnene.
- Det første elementet eller et vilkårlig element valgt som nøkkel, antar nøkkelen = A (1).
- Den "lave" pekeren er plassert på den andre og "opp" -pekeren er plassert på det siste elementet i gruppen, dvs. lav = 2 og opp = n;
- Øk konstant den "lave" pekeren med en posisjon til (A [low]> -tasten).
- Fortsett, senk "opp" -pekeren med en posisjon til (A [opp] <= tast).
- Hvis opp er større enn lav utveksling A [lav] med A [opp].
- Gjenta trinn 3, 4 og 5 til tilstanden i trinn 5 mislykkes (dvs. opp <= lav) og bytt ut A [opp] med tasten.
- Hvis elementene som er igjen av nøkkelen, er mindre enn nøkkelen, og elementene til høyre for nøkkelen er større enn nøkkelen, er arrayet delt inn i to delrader.
- Ovennevnte prosedyre brukes gjentatte ganger på underarrayene til hele oppstillingen er sortert.
Fordeler og ulemper
Den har en god gjennomsnittlig saksbehandling. Kjøretidskompleksiteten til den raske sorteringen er god, fordi den er raskere enn algoritmer som boble sortering, innføring sortering og utvalg sortering. Men det er komplekst og svært rekursivt, det er grunnen til at det ikke passer for store arrays.
Definisjon av Merge Sorter
Merge sort er en ekstern algoritme som også er basert på splittelse og erobre strategi. Elementene er delt i sub-arrays (n / 2) igjen og igjen til bare ett element er igjen, noe som reduserer sorteringstiden betydelig. Den bruker ekstra lagringsplass for å lagre tilleggsutstyret. Merge sort bruker tre arrays hvor to brukes til lagring av hver halvdel, og den tredje brukes til å lagre den endelige sorterte listen. Hver gruppe er deretter sortert rekursivt. Til slutt blir subarrays fusjonert for å gjøre det til en elementstørrelse av arrayet. Listen er alltid delt inn i bare halvparten (n / 2) ulik rask sortering.
La A være rekke av n antall elementer som skal sorteres A [1], A [2], ........., A [n]. Sammenslåingen følger de angitte trinnene.
- Del oppstillingen A i omtrent n / 2 sortert underarray med 2, noe som betyr at elementene i (A [1], A [2]), A [3], A [4] k], A [k + 1]), (A [n-1], A [n]) delarrayer må være i rekkefølge.
- Kombiner hvert par par for å oppnå listen over sorterte underarmer av størrelse 4; elementene i undergruppene er også i rekkefølge, (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]).
- Trinn 2 utføres gjentatte ganger til det bare er en sortert rekkevidde av størrelse n.
Fordeler og ulemper
Sammenslåingsalgoritmen utfører på nøyaktig samme og presise måte uavhengig av antall elementer som er involvert i sorteringen. Det fungerer fint selv med det store datasettet. Det bruker imidlertid større del av minnet.
Viktige forskjeller mellom hurtig sortering og sammenslåing Sorter
- I sammenslåingssorten må oppstillingen deles inn i bare to halvdeler (dvs. n / 2). I motsetning til, i rask sortering, er det ingen tvang om å dele listen i like elementer.
- Den verste kompleksiteten av rask sortering er O (n2), da det tar mye flere sammenligninger i verste tilstand. I motsetning til dette har flertallet det samme verste fallet og gjennomsnittskompleksiteten, det vil si O (n log n).
- Merge sort kan fungere godt på alle typer datasett om det er stort eller lite. Tvert imot kan den raske sorteringen ikke fungere godt med store datasett.
- Hurtig sortering er raskere enn fusjon sortere i noen tilfeller som for små datasett.
- Merge sort krever ekstra lagringsplass for å lagre tilleggsarrayene. På den annen side krever hurtig sortering ikke mye plass for ekstra lagring.
- Merge sort er mer effektiv enn rask sortering.
- Den raske sorteringen er intern sorteringsmetode der dataene som skal sorteres, justeres om gangen i hovedminnet. Omvendt er sammenslåingsvarianten ekstern sorteringsmetode der dataene som skal sorteres ikke kan innkvarteres i minnet samtidig, og noen må lagres i tilleggsminnet.
Konklusjon
Den raske sorteringen er raskere tilfeller, men er ineffektiv i noen situasjoner og utfører også mange sammenligninger sammenlignet med flette sortering. Selv om fusjonssortering krever mindre sammenligning, trenger den en ekstra minneplass på 0 (n) for lagring av ekstra array mens hurtig sortering trenger plass til O (log n).
