Hva er forskjellen mellom Quicksort og Merge Sort
Share
De hovedforskjell mellom quicksort og flette sortering er at quicksort sorterer elementene ved å sammenligne hvert element med et element som kalles en pivot mens sammenføyning sorterer oppdelingen i to subarrays igjen og igjen til et element er igjen.
Sortering er metoden for å ordne data i en bestemt rekkefølge. Når man skal ordne dataene, er det mulig å vurdere den numeriske eller leksikografiske rekkefølgen. Sortering bidrar til å søke og få tilgang til dataelementer raskere og raskere. Det finnes ulike sorteringsalgoritmer og quicksort og fusjonssort er to av dem.
Nøkkelområder dekket
1. Hva er Quicksort
- Definisjon, funksjonalitet
2. Hva er Merge Sorter
- Definisjon, funksjonalitet
3. Hva er forskjellen mellom Quicksort og Merge Sort
- Sammenligning av hovedforskjeller
Nøkkelord
Algoritme, Array, Flett Sorter, Quicksort
Hva er Quicksort
Quicksort er en intern algoritme som bruker "divide and conquer technique". Det kalles også en partisjon utveksling sortering. Den bruker et nøkkelelement kalt pivot for å sammenligne og partisjonere elementene i arrayet. Elementene med en mindre verdi enn svinget går til venstre side av sving mens varer med større verdi enn svinget går til høyre side av svinget. Den venstre delen kalles venstre partisjon, og den høyre delen heter den riktige partisjonen.
Figur 1: Quicksort
Se eksemplet nedenfor.
36 34 43 11 15 20 28 45 27 32
Vurder 32 som sving og vurder 36 og 27. Betingelsene 36 < pivot, 27 > pivot er falsk. Derfor kan vi bytte disse to verdiene. Nå er listen som følger.
27 34 43 11 15 20 28 45 36 32
Vurder verdiene 34 og 45. Når du vurderer 34 < pivot, the condition is false. Similarly, 45 > pivot tilstanden er sant. Nå kan vi flytte fra 45 til 28. La oss vurdere 34 og 28. 34 < pivot is false and 28 > pivot er feil. Derfor kan vi bytte 34 og 28.
27 28 43 11 15 20 34 45 36 32
Vurder 43 og 20. 43 < pivot is false. 20 > pivot er feil. Derfor kan vi bytte de to tallene. Nå er listen som følger.
27 28 20 11 15 43 34 45 36 32
Nå vurdere 11 og 15. 11 < pivot is true. We can consider 15. It is less than 32. It is the overlapping point, and we can place 32 as follows.
27 28 20 11 15 32 43 34 45 36
Nå er tallene i venstre side av svinget mindre enn svinget, og høyre side av svinget er større enn svinget. Vi kan søke quicksort til venstre og høyre partisjoner for å sortere hele listen.
Hva er Merge Sorter
Merge sort er en ekstern algoritme som bruker "divide and conquer technique". Det deler oppstillingen i to seksjoner. Det sorterer hver rekke og kombinerer dem sammen for å danne den sorterte matrisen. Merge-typen krever ekstra lagring for å sortere tilleggsarrangementet.
Vurder følgende eksempel.
Figur 2: Merge Sorter
Vi kan dele oppstillingen i to seksjoner. Nå er det to arrays som følger.
38 27 43 3 9 82 10
Vurder 38 27 43 3. Vi kan dele det i to arrays igjen. De er 38 27 og 43 3. 38 27 deler til 38 og 27 mens 43 3 deler i 43 og 3. Sortering 38 og 27 gir 27 38. Sortering 43 3 gir 3 43. Nå er det mulig å kombinere 27 38 og 3 43 Etter at vi sorterte dem, får vi en rekkefølge som 3 27 38 43.
På samme måte kan du vurdere 9 82 10. Vi kan dele det i to arrays igjen. De er 9 82 og 10. 9 82 deler i 9 og 82. Videre er det nummer 10 i den andre gruppen. 9 og 82 sorterer som 9 82. Således kombinerer og lager denne verdien og verdien med verdi 10 9 og 82.
Til slutt kombinerer 3 27 38 43 og 9 10 82 for å gi den sorterte matrisen.
Forskjellen mellom Quicksort og Merge Sorter
Definisjon
Quicksort er en effektiv sorteringsalgoritme, som fungerer som en systematisk metode for å plassere elementene i en matrise i rekkefølge. I motsetning til dette er flette sortering en effektiv, allsidig, sammenligningsbasert sorteringsalgoritme. Dermed er dette den grunnleggende forskjellen mellom quicksort og merge sort.
funksjonalitet
Fremfor alt er funksjonaliteten den viktigste forskjellen mellom quicksort og flette sortering. Quicksort sorterer elementene ved å sammenligne hvert element med pivot mens fusjon sorterer deler oppstillingen i to undergrupper (n / 2) igjen og igjen til ett element er igjen.
applikasjon
Også, mens quicksort passer for små arrays, fungerer flettesorter for alle typer array.
Hastighet
En annen forskjell mellom quicksort og merge sort er at quicksort fungerer raskere for små datasett mens kombinere sorterte arbeider i konsistent hastighet for alle datasett.
Plassbehov
Videre er plassbehovet også en viktig forskjell mellom quicksort og fusjonssort. Quicksort krever minimum plass sammenlignet med flette sortering.
Effektivitet
Videre er quicksort ikke effektivt for store arrays, men flette sortering er mer effektiv enn quicksort. Derfor er dette en annen forskjell mellom quicksort og flette sortering.
Konklusjon
I sammendraget er hovedforskjellen mellom quicksort og fusjonssort, at quicksorten sorterer elementene ved å sammenligne hvert element med et element som kalles en pivot mens fusjonssorteringen deler oppstillingen i to undergrupper igjen og igjen til ett element er igjen.
Henvisning:
1. Quicksort-algoritme | Del 2, Utdanning 4u, 15. mars 2018, Tilgjengelig her.
2. Merge Sorter Eksempel, Utdanning 4u, 15 Mar. 2018, Tilgjengelig her.
Bilde Courtesy:
1. "Quicksort-diagram" Av Znupi - Eget arbeid (Public Domain) via Commons Wikimedia
2. "Merge sort algoritm diagram" Av Vineet Kumar på engelsk Wikipedia - Overført fra en.wikipedia til Commons av Eric Bauman ved hjelp av CommonsHelper (Public Domain) via Commons Wikimedia
