Indhold

• Sammenligningstabel
• Definition af hurtig sortering
• Definition af fletningssortering
• Konklusion

Den hurtige sortering og fletningssorteringsalgoritmer er baseret på dividerings- og erobringsalgoritmen, der fungerer på en ganske lignende måde. Den forudgående forskel mellem sorteringen hurtig og fletning er, at drejelementet i hurtig sortering bruges til sorteringen. På den anden side bruger flettsorter ikke pivotelement til udførelse af sorteringen.

Både sorteringsteknikker, hurtig sortering og fletningssortering er bygget på split og erobre metoden, hvor sættet af elementer deles og derefter kombineres efter omarrangement. Den hurtige sortering kræver normalt flere sammenligninger end sammenfletningssortering for at sortere et stort sæt elementer.

1. 1. Sammenligningstabel
   2. Definition
   3. Vigtige forskelle
   4. Konklusion

Sammenligningstabel

Grundlag for sammenligning	Hurtig sortering	Flet sortering
Opdeling af elementerne i matrixen	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	På2)	O (n log n)
Fungerer godt	Mindre matrix	Fungerer fint i alle typer array.
Hastighed	Hurtigere end andre sorteringsalgoritmer til små datasæt.	Konsekvent hastighed i alle typer datasæt.
Ekstra krav til lagerplads	Mindre	Mere
Effektivitet	Ineffektiv til større matriser.	Mere effektivt.
Sorteringsmetode	Indre	Udvendig

Definition af hurtig sortering

Hurtig sortering bruges gennemgående sorteringsalgoritme, da den er hurtig til de korte arrays. Sættet med elementerne er opdelt gentagne gange i dele, indtil det ikke er muligt at opdele det yderligere. Hurtig sortering kaldes også partition udveksling sortering. Det bruger et nøgleelement (kendt som pivot) til at opdele elementerne. Én 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, at A er en matrix A, A, A, …… .., A med n-nummer, der skal sorteres. Den hurtige sorteringsalgoritme består af følgende trin.

1. Det første element eller ethvert tilfældigt element valgt som nøgle, antager nøgle = A (1).
2. Den "lave" markør placeres ved den anden, og "op" -pekeren er placeret ved det sidste element i array, dvs. lav = 2 og op = n;
3. Forøg konsekvent den “lave” markør med en position indtil (A> -tasten).
4. Dekreter konstant “op” -viseren med en position indtil (A <= -tasten).
5. Hvis op er større end lav veksling A med A.
6. Gentag trin 3,4 og 5, indtil betingelsen i trin 5 mislykkes (dvs. op <= lav), skift derefter A med nøglen.
7. Hvis elementerne til venstre for nøglen er mindre end nøglen, og elementerne til højre for nøglen er større end nøglen, opdeles arrayet i to underarrays.
8. Ovenstående procedure anvendes gentagne gange på undergrænserne, indtil hele matrixen er sorteret.

   

   
   

Fordele og ulemper

Det har en god gennemsnitlig sagsadfærd. Den hurtige sorteres driftstidskompleksitet er god, det er, at den er hurtigere end algoritmer såsom boble sortering, indsættelsessortering og valg af sortering. Det er imidlertid komplekst og meget rekursivt, det er grunden til, at det ikke er egnet til store matriser.

Definition af fletningssortering

Flet sortering er en ekstern algoritme, som også er baseret på split og erobre strategi. Elementerne er opdelt i undergrupper (n / 2) igen og igen, indtil der kun er et element tilbage, hvilket reducerer sorteringstiden markant. Den bruger ekstra lagerplads til opbevaring af hjælpearrangementet. Flet sortering bruger tre arrays, hvor to bruges til opbevaring af hver halvdel, og den tredje bruges til at gemme den endelige sorterede liste. Hver matrix sorteres derefter rekursivt. Til sidst flettes delområderne for at gøre det til elementets størrelse. Listen er altid opdelt i kun halvdelen (n / 2), der er forskellig fra hurtig sortering.

Lad A være matrixen af ​​n antal elementer, der skal sorteres A, A, ………, A. Flettesorteringen følger de givne trin.

1. Opdel array A i ca. n / 2-sorteret underarray med 2, hvilket betyder, at elementerne i (A, A), (A, A), (A, A), (A, A) underarrays skal være i sorteret rækkefølge.
2. Kombiner hvert par par for at få listen over sorterede undergrænser i størrelse 4; elementerne i undergrænserne er også i sorteret rækkefølge, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Trin 2 udføres gentagne gange, indtil der kun er en sorteret matrix med størrelse n.

   

Fordele og ulemper

Flettsorteringsalgoritmen udføres på nøjagtig samme og præcise måde uanset antallet af elementer, der er involveret i sorteringen. Det fungerer fint selv med det store datasæt. Dog bruger den større del af hukommelsen.

1. I sammenfletningen skal arrayet opdeles i kun to halvdele (dvs. n / 2). I modsætning hertil er der ingen hurtig forpligtelse til at opdele listen i lige store elementer.
2. Det værste tilfælde kompleksitet af hurtig sortering er O (n²) da det kræver meget mere sammenligning i værste stand. I modsætning hertil har flettsorter den samme worst case og gennemsnitlige kompleksitet, dvs. O (n log n).
3. Flettsortering kan fungere godt på alle typer datasæt, uanset om det er stort eller lille. Tværtimod, den hurtige sortering kan ikke fungere godt med store datasæt.
4. Hurtig sortering er hurtigere end flettsortering i nogle tilfælde, f.eks. For små datasæt.
5. Flettsortering kræver yderligere hukommelsesplads til at gemme hjælpearrangierne. På den anden side kræver den hurtige sortering ikke meget plads til ekstra lagerplads.
6. Flettesortering er mere effektiv end hurtig sortering.
7. Den hurtige sortering er intern sorteringsmetode, hvor de data, der skal sorteres, justeres ad gangen i hovedhukommelsen. Omvendt er fusionen sortering ekstern sorteringsmetode, hvor de data, der skal sorteres, ikke kan rumme i hukommelsen på samme tid, og nogle skal opbevares i hjælpehukommelsen.

Konklusion

Den hurtige sortering er hurtigere sager, men er ineffektiv i nogle situationer og udfører også en masse sammenligninger sammenlignet med sammenfletningssortering. Selvom fletningssortering kræver mindre sammenligning, har den brug for en ekstra hukommelsesplads på 0 (n) til lagring af den ekstra matrix, mens hurtig sortering har brug for plads til O (log n).