Vad är skillnaden mellan Quicksort och Merge Sort

De huvudskillnad mellan quicksort och merge sort är att quicksort sorterar elementen genom att jämföra varje element med ett element som kallas en pivot medan sammanfogning sorterar uppdelningen i två subarrays om och om igen tills ett element lämnas.

Sortering är metoden för att ordna data i en viss ordning. Vid ordningen av data är det möjligt att överväga den numeriska eller lexikografiska ordningen. Sortering hjälper till att söka och få tillgång till dataelement snabbare och snabbare. Det finns olika sorteringsalgoritmer och quicksort och merge sort är två av dem.

Viktiga områden som omfattas

1. Vad är Quicksort
     - Definition, Funktionalitet
2. Vad är Merge Sort
     - Definition, Funktionalitet
3. Vad är skillnaden mellan Quicksort och Merge Sort
     - Jämförelse av viktiga skillnader

Nyckelbegrepp

Algoritm, Array, Sammanfoga Sortera, Quicksort

Vad är Quicksort

Quicksort är en intern algoritm som använder "dela och erövra teknik". Det kallas också en partitionsbytes sortering. Den använder ett nyckelelement som kallas pivot för att jämföra och partitionera elementen i matrisen. Föremålen med ett mindre värde än vridningen går till vänster om pivot medan objekt med ett större värde än vridningen går till höger om vridningen. Den vänstra delen heter den vänstra partitionen, och den högra delen heter rätt partition.

Figur 1: Quicksort

Se nedan exempel.

36 34 43 11 15 20 28 45 27 32

Betrakta 32 som pivot och betrakta 36 och 27. Villkoren 36 < pivot, 27 > pivot är falskt. Därför kan vi byta dessa två värden. Nu är listan som följer.

27 34 43 11 15 20 28 45 36 32

Tänk på värdena 34 och 45. När man överväger 34 < pivot, the condition is false. Similarly, 45 > svängförhållandet är sant. Nu kan vi flytta från 45 till 28. Låt oss överväga 34 och 28. 34 < pivot is false and 28 > pivot är falskt. Därför kan vi byta 34 och 28.

27 28 43 11 15 20 34 45 36 32

Tänk på 43 och 20. 43 < pivot is false. 20 > pivot är falskt. Därför kan vi byta de två siffrorna. Nu är listan som följer.

27 28 20 11 15 43 34 45 36 32

Nu överväga 11 och 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 

Nu är siffrorna i vänster sida av vridmomentet mindre än vridningen, och höger sida av vridmomentet är större än vridningen. Vi kan ansöka quicksort till vänster och höger partition för att sortera hela listan.

Vad är Merge Sort

Merge sort är en extern algoritm som använder "divide and conquer technique". Det delar upp arrayen i två sektioner. Det sorterar varje matris och kombinerar dem tillsammans för att bilda den sorterade matrisen. Sammanfoga sorterar kräver ytterligare lagring för att sortera hjälpprogrammet.

Tänk på följande exempel.

Figur 2: Merge Sortera

Vi kan dela upp arrayen i två sektioner. Nu finns det två arrays enligt följande.

38 27 43 3 9 82 10

Tänk på 38 27 43 3. Vi kan dela upp den i två arrays igen. De är 38 27 och 43 3. 38 27 delas i 38 och 27 medan 43 3 delas i 43 och 3. Sortering 38 och 27 ger 27 38. Sortering 43 3 ger 3 43. Nu är det möjligt att kombinera 27 38 och 3 43 Efter sortering får vi en array som 3 27 38 43. 

På samma sätt överväga 9 82 10. Vi kan dela upp den i två arrays igen. De är 9 82 och 10. 9 82 delar upp i 9 och 82. Dessutom finns det nummer 10 i den andra gruppen. 9 och 82 sortera som 9 82. Således kombinerar och uppställer denna grupp och array med värde 10 9 och 82.

Slutligen kombineras 3 27 38 43 och 9 10 82 för att tillhandahålla den sorterade matrisen.

Skillnad mellan Quicksort och Merge Sort

Definition

Quicksort är en effektiv sorteringsalgoritm, som fungerar som en systematisk metod för att placera elementen i en array i ordning. I motsats till detta är sammanslagning en effektiv, jämförelsebaserad sorteringsalgoritm för allmänt ändamål. Således är detta den grundläggande skillnaden mellan quicksort och merge sort.

Funktionalitet

Ovanför är funktionaliteten den viktigaste skillnaden mellan quicksort och merge sort. Quicksort sorterar elementen genom att jämföra varje element med pivotet medan sammanslagning sorterar uppdelningen i två subarrays (n / 2) om och om tills ett element lämnas.

Ansökan

Även om quicksort är lämpligt för små arrays fungerar sammanslagnings sorter för alla typer av array.

Fart

En annan skillnad mellan quicksort och merge sort är att quicksort fungerar snabbare för små dataset medan fusionerar sortera arbeten i jämn hastighet för alla dataset.

Utrymme krav

Dessutom är rymdkravet också en viktig skillnad mellan quicksort och merge sort. Quicksort kräver minimalt utrymme jämfört med sammanslagningssort.  

Effektivitet

Dessutom är quicksort inte effektivt för stora arrays, men sammanslagning är effektivare än quicksort. Det här är en annan skillnad mellan quicksort och merge sort.

Slutsats

Sammanfattningsvis är den huvudsakliga skillnaden mellan quicksort och merge sorten att quicksorten sorterar elementen genom att jämföra varje element med ett element som kallas en pivot medan sammanslagningssorten delar upp arrayen i två undergrupper om och om igen tills ett element lämnas.

Referens:

1. Quicksort-algoritm | Del 2, Utbildning 4u, 15 mars 2018, Tillgänglig här.
2. Sammanfoga Sortera Exempel, Utbildning 4u, 15 Mars 2018, Tillgänglig här.

Image Courtesy:

1. "Quicksort-diagram" Av Znupi - Egent arbete (Public Domain) via Commons Wikimedia
2. "Merge sort algoritm diagram" Av Vineet Kumar på engelska Wikipedia - Överförd från en.wikipedia till Commons av Eric Bauman med CommonsHelper (Public Domain) via Commons Wikimedia