Både sorteringsteknikker, hurtig sortering og sammensmeltning sorteres på dividen og erobre metoden, hvor sæt af elementer er adskilt og derefter kombineret efter omlægning. Den hurtige sortering kræver normalt flere sammenligninger end flette sort for at sortere et stort sæt elementer.
Sammenligningstabel
| Grundlag for sammenligning | Hurtig sortering | Flet sort |
|---|---|---|
| Opdeling af elementerne i arrayet | Opdelingen af en liste over elementer er ikke nødvendigvis opdelt i halvdelen. | Array er altid opdelt i halvdelen (n / 2). |
| Værste tilfælde kompleksitet | O (n2) | O (n log n) |
| Fungerer godt | Mindre array | Fungerer fint i enhver type array. |
| Hastighed | Hurtigere end andre sorteringsalgoritmer til små datasæt. | Konsekvent hastighed i alle typer datasæt. |
| Yderligere lagerplads krav | Mindre | Mere |
| Effektivitet | Ineffektive til større arrays. | Mere effektivt. |
| Sorteringsmetode | Indre | Udvendig |
Definition af hurtig sortering
Hurtig sortering er pervasivt brugt sorteringsalgoritme, da det er hurtigt for de korte arrayer. Sættet af elementerne er opdelt i dele gentagne gange, indtil det ikke er muligt at opdele det yderligere. Hurtig sortering er også kendt som partitionsbytter sortering . Det bruger et nøgleelement (kendt som pivot) til partitionering af elementerne. En partition indeholder de elementer, der er mindre end nøgleelementet. En anden partition indeholder de elementer, der er større end nøgleelementet. Elementerne sorteres rekursivt.
Antag A er et array A [1], A [2], A [3], ...... .., A [n] af n nummer, der skal sorteres. Den hurtige sorteringsalgoritme består af de følgende trin.
- Det første element eller et vilkårligt element valgt som nøgle, antager nøgle = A (1).
- Den "lave" pointer er placeret ved den anden og "op" -pegeren er placeret ved det sidste element i arrayet, dvs. lav = 2 og op = n;
- Øg konstant stigningen "lav" med en position til (A [low]> -tasten).
- Konstant reducere "op" -pegeren med en position til (A [op] <= nøgle).
- Hvis op er større end lav udveksling A [lav] med A [op].
- Gentag trin 3, 4 og 5, indtil tilstanden i trin 5 fejler (dvs. op <= lav) og udskift A [op] med tasten.
- Hvis de elementer, der er tilbage af nøglen, er mindre end nøglen, og elementernes højre side er større end nøglen, er arrayet opdelt i to underarrayer.
- Ovennævnte procedure anvendes gentagne gange på underarrayerne, indtil hele arrayet er sorteret.
Fordele og ulemper
Den har en god gennemsnitlig sagsadfærd. Komplettheden i hurtig sorteringen er god, da den er hurtigere end algoritmer som f.eks. Sortering af bobler, indsætnings sorter og valg sortering. Men det er komplekst og meget rekursivt, det er grunden til, at det ikke passer til store arrays.
Definition af flette sortering
Flet sort er en ekstern algoritme, som også er baseret på opdeling og erobre strategi. Elementerne er opdelt i subarrayer (n / 2) igen og igen, indtil kun et element er tilbage, hvilket reducerer sorteringstiden betydeligt. Den bruger ekstra lagerplads til opbevaring af hjælpearrangementet. Sammensætning sorterer bruger tre arrays, hvor to bruges til opbevaring af hver halvdel, og den tredje bruges til at gemme den endelige sorterede liste. Hvert array sorteres derefter rekursivt. Endelig føjes subarraysne til at gøre det n elementstørrelse af arrayet. Listen er altid opdelt i kun halvdelen (n / 2), der er forskellig fra hurtig sortering.
Lad A være arrayet af n antal elementer, der skal sorteres A [1], A [2], ........., A [n]. Sammensætningen følger de givne trin.
- Opdel array A til ca. n / 2 sorteret under array med 2, hvilket betyder at elementerne i (A [1], A [2]), (A [3], A [4]), k], A [k + 1]), (A [n-1], A [n]) subarrayer skal være i rækkefølge.
- Kombinér hvert par par for at få listen over sorterede subarrays af størrelse 4; elementerne i subarrays er også i rækkefø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]).
- Trinet 2 udføres gentagne gange, indtil der kun er en sorteret array med størrelse n.
Fordele og ulemper
Sammensmeltningsalgoritmen udfører på nøjagtig samme og præcise måde uanset antallet af elementer involveret i sorteringen. Det virker fint selv med det store datasæt. Det forbruger imidlertid større del af hukommelsen.
Nøgleforskelle mellem hurtig sortering og flette sortering
- I fusionssortet skal opstillingen deles i kun to halvdele (dvs. n / 2). I modsætning til, i hurtig sortering er der ingen tvang om at opdele listen i ensartede elementer.
- Den sværeste kompleksitet af hurtig sortering er O (n2), da det kræver meget flere sammenligninger i værste tilstand. I modsætning hertil har fusionssortimentet det samme værste tilfælde og gennemsnitskompleksiteter, det vil sige O (n log n).
- Flet sort kan fungere godt på alle typer datasæt, uanset om den er stor eller lille. Tværtimod kan den hurtige sortering ikke fungere godt med store datasæt.
- Hurtig sortering er hurtigere end sammenfletning i nogle tilfælde som for små datasæt.
- Sammensmeltningssort kræver yderligere hukommelsesplads til at gemme hjælpestrukturerne. På den anden side kræver hurtig sorten ikke meget plads til ekstra opbevaring.
- Flet sort er mere effektiv end hurtig sortering.
- Den hurtige sortering er intern sorteringsmetode, hvor dataene, der skal sorteres, justeres ad gangen i hovedhukommelsen. Omvendt er fusionssorteringen ekstern sorteringsmetode, hvor de data, der skal sorteres, ikke kan optages i hukommelsen på samme tid, og nogle skal opbevares i hjælpeminnet.
Konklusion
Den hurtige sortering er hurtigere tilfælde, men er ineffektiv i nogle situationer og udfører også mange sammenligninger sammenlignet med flette sortering. Selvom flette sorter kræver mindre sammenligning, har den brug for en ekstra hukommelsesplads på 0 (n) til opbevaring af det ekstra array, mens hurtig sortering kræver plads til O (log n).
