Innhold

• Sammenligningstabell
• Definisjon av Quick Sort
• Definisjon av Merge Sort
• Konklusjon

De raske sorterings- og flettesorteringsalgoritmene er basert på skillet og erobringsalgoritmen som fungerer på ganske lik måte. Den tidligere forskjellen mellom hurtig og flett sortering er at i hurtig sortering brukes pivotelementet til sorteringen. På den annen side bruker ikke flette sortering pivotelement for å utføre sorteringen.

Både sorteringsteknikker, hurtig sortering og sammenslåingssortering er bygget på skillet og erobre metoden der settet med elementer deles og deretter kombineres etter omorganisering. Den raske sorteringen krever vanligvis flere sammenligninger enn flettingsortering for å sortere et stort sett med elementer.

1. 1. Sammenligningstabell
   2. Definisjon
   3. Viktige forskjeller
   4. Konklusjon

Sammenligningstabell

Grunnlag for sammenligning	Rask sortering	Slå sammen sortering
Partisjonering av elementene i matrisen	Delingen av en liste over elementer er ikke nødvendigvis delt i halvparten.	Array er alltid delt i halvparten (n / 2).
Verste tilfelle kompleksitet	På2)	O (n log n)
Fungerer bra	Mindre utvalg	Fungerer fint i alle typer matriser.
Hastighet	Raskere enn andre sorteringsalgoritmer for lite datasett.	Konsekvent hastighet i alle typer datasett.
Ekstra krav til lagringsplass	Mindre	Mer
Effektivitet	Ineffektivt for større matriser.	Mer effektivt.
Sorteringsmetode	Innvendig	Utvendig

Definisjon av Quick Sort

Rask sortering brukes gjennomgripende sorteringsalgoritme da den er rask for de korte arrayene. Settet av elementene er delt inn i deler gjentatte ganger til det ikke er mulig å dele det videre. Rask sortering er også kjent som partisjon utveksling sortere. Den bruker et nøkkelelement (kjent som pivot) for å dele elementene. En partisjon inneholder elementene som er mindre enn nøkkelelementet. En annen partisjon inneholder de elementene som er større enn nøkkelelementet. Elementene blir sortert rekursivt.

Anta at A er en matrise A, A, A, …… .., A med n-nummer som må sorteres. Den raske sorteringsalgoritmen består av følgende trinn.

1. Det første elementet eller et hvilket som helst tilfeldig element valgt som nøkkel, antar tasten = A (1).
2. Den "lave" pekeren plasseres ved den andre og "opp" pekeren er plassert ved det siste elementet i arrayen, dvs. lav = 2 og opp = n;
3. Øk konsekvent den "lave" pekeren med én posisjon til (A> -tasten).
4. Begrens konstant "opp" -pekeren med én posisjon til (A <= -tasten).
5. Hvis opp er større enn lav veksling A med A.
6. Gjenta trinn 3,4 og 5 til tilstanden i trinn 5 mislykkes (dvs. opp <= lav) og bytt deretter inn A med tasten.
7. Hvis elementene til venstre for nøkkelen er mindre enn nøkkelen og elementene til høyre for nøkkelen er større enn nøkkelen, blir arrayet delt inn i to underarrayer.
8. Ovennevnte prosedyre blir gjentatte ganger brukt på delområdene til hele matrisen er sortert.

   

   
   

Fordeler og ulemper

Det har en god gjennomsnittlig saksatferd. Kjøretidskompleksiteten til den raske sorteringen er god, det vil si at den er raskere enn algoritmer som boble sortering, innsetting sortering og valg sortering. Imidlertid er den kompleks og veldig rekursiv, det er grunnen til at den ikke er egnet for store matriser.

Definisjon av Merge Sort

Slå sammen sortering er en ekstern algoritme som også er basert på skill og erobre strategi. Elementene blir delt opp i delarrayer (n / 2) igjen og igjen til bare ett element er igjen, noe som reduserer sorteringstiden betydelig. Den bruker ekstra lagring for lagring av hjelpearrayen. Merge sort bruker tre matriser der to brukes til lagring av hver halvdel, og den tredje brukes til å lagre den endelige sorterte listen. Hver gruppe sorteres deretter rekursivt. Til slutt blir delområdene slått sammen slik at det blir en elementstørrelse på matrisen. Listen er alltid delt inn i bare halvparten (n / 2) ulik rask sortering.

La A være matrisen av n antall elementer som skal sorteres A, A, ..........., A. Slå sammen sorteringen følger de gitte trinn.

1. Del matrisen A i omtrent n / 2-sortert delarray med 2, noe som betyr at elementene i (A, A), (A, A), (A, A), (A, A) delarrayer må være i sortert rekkefølge.
2. Kombiner hvert par par for å få listen over sorterte delområder i størrelse 4; elementene i delområdene er også i sortert rekkefølge, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Trinn 2 utføres gjentatte ganger til det bare er en sortert matrise med størrelse n.

   

Fordeler og ulemper

Sammenslåingssorteringsalgoritmen utfører på nøyaktig samme og presise måte uavhengig av antall elementer som er involvert i sorteringen. Det fungerer bra selv med det store datasettet. Imidlertid bruker den større del av minnet.

1. I sammenslåingssorteringen må matrisen deles inn i bare to halvdeler (dvs. n / 2). I motsatt fall er det ingen tvang om å dele listen i like elementer.
2. Det verste tilfelle av hurtig sortering er O (n²) da det krever mye mer sammenligning i dårligste stand. I motsetning til dette, har sammenslåingssortering den samme worst case og gjennomsnittlige sakskompleksiteter, det vil si O (n log n).
3. Merge sort kan fungere godt på alle typer datasett, enten det er stort eller lite. Tvert imot, den raske sorteringen kan ikke fungere bra med store datasett.
4. Rask sortering er raskere enn flettesortering i noen tilfeller, for eksempel for små datasett.
5. Merge sort krever ekstra minneplass for å lagre hjelpearrangene. På den annen side krever den raske sorteringen ikke mye plass for ekstra lagring.
6. Merge sort er mer effektivt enn hurtig sortering.
7. Den raske sorteringen er intern sorteringsmetode der dataene som skal sorteres justeres om gangen i hovedminnet. Motsatt er sammenslåingssorteringen ekstern sorteringsmetode der dataene som skal sorteres ikke kan tas imot i minnet på samme tid, og noen må oppbevares i hjelpeminnet.

Konklusjon

Den raske sorteringen er raskere tilfeller, men er ineffektiv i noen situasjoner og utfører også mange sammenligninger sammenlignet med sammenslåingssortering. Selv om flettesortering krever mindre sammenligning, trenger den en ekstra minneplass på 0 (n) for å lagre den ekstra matrisen mens rask sortering trenger plass til O (log n).