Rask sort vs Merge Sort sammenlignet

“Målet med denne artikkelen er å gi likhetene og forskjellene mellom rask sortering og flettesorter. Artikkelen "Quick Sort in C," eller en lignende tittel, er allerede skrevet for Linuxhint.com/. Tittelen kan skrives i søkeboksen til Linuxhint.com hjemmeside for å nå artikkelen. En annen artikkel, "Merge Sort in C," eller en lignende tittel, er allerede skrevet for Linuxhint.com/. Tittelen kan skrives i søkeboksen til Linuxhint.com hjemmeside for å nå artikkelen. Leseren anbefales å referere til de to artiklene mens han/hun leser denne.

Rask sorter er en sorteringsalgoritme. Merge -sort er en annen sorteringsalgoritme. Koden for de to artiklene som er nevnt ovenfor er skrevet i C. Kode for denne artikkelen er også skrevet i C. Leseren skal være klar over det. Sort stigende blir vurdert for begge sortering algoritmer i denne artikkelen.”

Artikkelinnhold

- INNLEDNING - Se ovenfor
- Algoritmer for rask sort og smelter sort
- Big-O-notasjon av o (n), o (n2) og o (n.logg (n))
- Sammenligning av rask sorter og smelter sort
- Konklusjon

Algoritmer for rask sort og smelter sort
Algoritme for Quicksort

1) Hvis det bare er ett eller ingen element på listen, kan du returnere. Ett element betyr at listen allerede er sortert. Null element betyr at det ikke er noe å sortere.
2) Med en intelligent gjetning, velg et passende element på listen som en pivot.
3) Partisjon (del) listen i tre underlister. Lag alle elementene for venstre underliste mindre enn pivoten. Den sentrale listen har bare ett element, som er pivoten. Gjør alle elementene på riktig underliste større enn pivoten. Ved å sette elementer til venstre som er mindre enn pivoten, og elementene til høyre som er større enn pivoten, uten ren sortering, er det allerede en sortering (i bred forstand).
4) Del rekursivt hver underliste (venstre og høyre) i tre, som i trinnet ovenfor, med hvert sett med tre underlister som har sin egen nye pivot (av ett element underliste), inntil hele den gitte listen er perfekt sortert.

Det er forskjellige kodingsformer for trinn 2. En bedre kodingsform vil føre til raskere fullstendig sortering.
Det er forskjellige kodingsformer for trinn 3. En bedre kodingsform vil føre til raskere fullstendig sortering.

Algoritme for sammenslåing

1) Hvis det bare er ett eller ingen element på listen, kan du returnere. Ett element betyr at listen allerede er sortert. Null element betyr at det ikke er noe å sortere.
2) Del rekursivt listen og underlisten i to halvdeler til hver underliste bare har ett element.
3) Sorter par underlister fra venstre til høyre rekursivt, inkludert resulterende større par, inntil hele listen er gjenvunnet, men fullstendig sortert.

Dette er den normale måten å gjøre sammenslåing, og det gir egentlig ikke rom, for forskjellige kodesegmenter, for samme formål som Quicksort gjør.

Big-O-notasjon av o (n), o (n2) og o (n.logg (n))

På)
Tenk på følgende kode:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
for (int i = 0; isum = sum + a [i];

printf ("%d \ n", sum);

n = 8. Utgangen, summen er 36. I for-loop er det en operasjon som utføres 8 ganger. I Big-O-notasjonen er denne hastigheten (tidskompleksitet) skrevet som,

På)

Tenk på følgende lignende kode, der bare oddetallene er lagt til:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
for (int i = 0; isum = sum + a [i];

printf ("%d \ n", sum);

Utgangen, summen denne gangen, er 16. I for-loop utføres den ene operasjonen 4 ganger, som er n/2 ganger. I Big-O-notasjonen er denne hastigheten (tidskompleksitet) fremdeles skrevet som O (n). Det maksimale antallet mulige operasjoner er det som blir vurdert.

På²)

Tenk på følgende kode som legger til matrisen på 8-til-8-tall:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
for (int i = 0; ifor (int j = 0; jsum = sum + a [j];


printf ("%d \ n", sum);

Utgangen, summen, er 288. I for-loop er det en operasjon som utføres 8 x 8 ganger = 64 ganger. I Big-O-notasjonen er denne hastigheten (tidskompleksitet) skrevet som,

O (n²)

Tenk på følgende lignende kode, der bare oddetall på matrisen er lagt til:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
for (int i = 0; ifor (int j = 0; jsum = sum + a [j];


printf ("%d \ n", sum);

Utgangen, summen denne gangen, er 64. I for-loop utføres den ene operasjonen 4 x 4 ganger = 16 ganger, som er n²/4 ganger. Dette er mer enn 8 ganger (mer enn n ganger), men mindre enn 64 ganger (mindre enn n² tider). I Big-O-notasjonen kan denne hastigheten (tidskompleksitet) fremdeles skrives som O (n²). Det maksimale antallet mulige operasjoner er det som blir vurdert.

Her, ikke forveksle summen, 64, og antall operasjoner, 16. Denne saken om 16 operasjoner, mellom 8 (n) og 64 (n²), kan fremdeles skrives, som i følgende underavsnitt.

På.logg (n))

Tenk på situasjonen til en 8-by-8-matrise, der det totale antallet operasjoner er 24. 24 kan sees på å være omtrent rundt midten, mellom 8 (n) og 64 (n²).

Nå,

24 = 8xlog₂(8)
=> 24 = 8xlog₂(2³)
=> 24 = 8 × 3

Nå sammenligne,

24 = 8xlog₂(8)
med
24 = n.Logg₂(n)

For maksimalt n², Når det totale antallet operasjoner er mellom n og n², Og rundt midten, i Big-O-notasjonen, er denne hastigheten (tidskompleksitet) bedre skrevet som n.Logg₂(n) i stedet for o (n²).

Sammenligning av rask sorter og smelter sort
Antall trinn i algoritmen

Over ovenfra har Quicksort 4 trinn i algoritmen, mens Fusjonsort har 3 trinn i algoritmen.

Ulike måter å kode

Rask sort har forskjellige måter å koding på, mens Merge Sort bare har en hoved måte å kode på.

Tidskompleksitet

Tidskompleksiteten for sammenslåing er n.Logg₂(n). Hastigheten er sammenlignbar med den for sorteringsfunksjonen til C ++ biblioteket som brukes til kommersielle formål.

Når median pivotfunksjon brukes til Quicksort, er tidskompleksiteten omtrent 1.188n.Logg₂(n), høyere enn sammenslåing, forutsatt at en god partisjonsfunksjon brukes. Mange Quicksort -programmer har høyere tidskompleksitet. Den verste tidskompleksiteten for Quicksort er o (n²). Imidlertid, hvis Quicksort -programmet er godt kodet med veldig gode kodesegmenter, ville det slå MergeSort i hastighet.

Konklusjon

Quicksort kjører normalt saktere enn Fusjoner.