Anbefalet, 2021

Redaktørens Valg

Forskel mellem Quick Sort og Merge Sort

De hurtige sorterings- og fusionssortalgoritmer er baseret på divideringen og erobrer algoritmen, som virker på samme måde. Den forudgående forskel mellem hurtig- og fusionssorteringen er, at ved hurtig sortering anvendes pivotelementet til sorteringen. På den anden side bruger fusionssortiment ikke pivotelement til at udføre sorteringen.

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 sammenligningHurtig sorteringFlet sort
Opdeling af elementerne i arrayetOpdelingen af ​​en liste over elementer er ikke nødvendigvis opdelt i halvdelen.Array er altid opdelt i halvdelen (n / 2).
Værste tilfælde kompleksitetO (n2)O (n log n)
Fungerer godtMindre arrayFungerer fint i enhver type array.
HastighedHurtigere end andre sorteringsalgoritmer til små datasæt.Konsekvent hastighed i alle typer datasæt.
Yderligere lagerplads kravMindreMere
EffektivitetIneffektive til større arrays.Mere effektivt.
SorteringsmetodeIndreUdvendig

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.

  1. Det første element eller et vilkårligt element valgt som nøgle, antager nøgle = A (1).
  2. 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;
  3. Øg konstant stigningen "lav" med en position til (A [low]> -tasten).
  4. Konstant reducere "op" -pegeren med en position til (A [op] <= nøgle).
  5. Hvis op er større end lav udveksling A [lav] med A [op].
  6. Gentag trin 3, 4 og 5, indtil tilstanden i trin 5 fejler (dvs. op <= lav) og udskift A [op] med tasten.
  7. 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.
  8. 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.

  1. 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.
  2. 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]).
  3. 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

  1. 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.
  2. 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).
  3. 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.
  4. Hurtig sortering er hurtigere end sammenfletning i nogle tilfælde som for små datasæt.
  5. Sammensmeltningssort kræver yderligere hukommelsesplads til at gemme hjælpestrukturerne. På den anden side kræver hurtig sorten ikke meget plads til ekstra opbevaring.
  6. Flet sort er mere effektiv end hurtig sortering.
  7. 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).

Top