Wat is het verschil tussen Quicksort en samenvoegsortering
Share
De grootste verschil tussen quicksort en merge sort is dat het quicksort sorteert de elementen door elk element te vergelijken met een element dat een draaipunt wordt genoemd, terwijl samenvoegselectie de array keer op keer verdeelt in twee subarrays totdat een element overblijft.
Sorteren is de methode om gegevens in een bepaalde volgorde te rangschikken. Bij het ordenen van de gegevens is het mogelijk om de numerieke of lexicografische volgorde te beschouwen. Sorteren helpt om gegevenselementen sneller en sneller te zoeken en openen. Er zijn verschillende sorteeralgoritmen en quicksort en merge sortering zijn er twee.
Key Areas Covered
1. Wat is QuickSort
- Definitie, functionaliteit
2. Wat is Merge Sort
- Definitie, functionaliteit
3. Wat is het verschil tussen Quicksort en samenvoegsortering
- Vergelijking van belangrijke verschillen
Sleutelbegrippen
Algoritme, matrix, samenvoegsortering, quicksort
Wat is QuickSort
QuickSort is een intern algoritme dat gebruik maakt van de 'verdeel en heers techniek'. Het wordt ook genoemd een soort partitie-uitwisseling. Het gebruikt een sleutelelement genaamd draaipunt voor het vergelijken en partitioneren van de elementen in de array. De items met een lagere waarde dan het draaipunt gaan naar de linkerkant van het draaipunt terwijl items met een grotere waarde dan het draaipunt naar de rechterkant van het draaipunt gaan. De linker sectie wordt de linker partitie genoemd, en de rechter sectie wordt de rechter partitie genoemd.
Figuur 1: Quicksort
Raadpleeg het onderstaande voorbeeld.
36 34 43 11 15 20 28 45 27 32
Beschouw 32 als het draaipunt en overweeg 36 en 27. De voorwaarden 36 < pivot, 27 > draaipunt is vals. Daarom kunnen we deze twee waarden omwisselen. Nu is de lijst als volgt.
27 34 43 11 15 20 28 45 36 32
Beschouw de waarden 34 en 45. Bij overweging 34 < pivot, the condition is false. Similarly, 45 > draaitoestand is waar. Nu kunnen we van 45 naar 28 gaan. Laten we 34 en 28 beschouwen. 34 < pivot is false and 28 > spil is niet waar. Daarom kunnen we 34 en 28 ruilen.
27 28 43 11 15 20 34 45 36 32
Beschouw 43 en 20. 43 < pivot is false. 20 > spil is niet waar. Daarom kunnen we de twee nummers omwisselen. Nu is de lijst als volgt.
27 28 20 11 15 43 34 45 36 32
Beschouw nu 11 en 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 zijn de cijfers aan de linkerkant van het draaipunt kleiner dan het draaipunt en de rechterkant van het draaipunt groter dan het draaipunt. We kunnen quicksort toepassen op de linker en rechter partities om de volledige lijst te sorteren.
Wat is Merge Sort
Samenvoegsortering is een extern algoritme dat gebruik maakt van 'verdeel en heers techniek'. Het verdeelt de array in twee secties. Het sorteert elke array en combineert ze samen om de gesorteerde array te vormen. Samenvoegen sortering vereist extra opslag om de hulparray te sorteren.
Bekijk het volgende voorbeeld.
Figuur 2: Sortering samenvoegen
We kunnen de array in twee delen verdelen. Nu zijn er twee arrays als volgt.
38 27 43 3 9 82 10
Overweeg 38 27 43 3. We kunnen het opnieuw in twee reeksen verdelen. Ze zijn 38 27 en 43 3. 38 27 zijn verdeeld in 38 en 27 terwijl 43 3 zich in 43 en 3 verdeelt. Sortering 38 en 27 geeft 27 38. Sorteren 43 3 levert 3 43 op. Nu is het mogelijk om 27 38 en 3 43 te combineren Nadat we ze hebben gesorteerd, krijgen we een array als 3 27 38 43.
Overweeg ook 9 82 10. We kunnen het opnieuw in twee reeksen verdelen. Ze zijn 9 82 en 10. 9 82 deelt zich in 9 en 82. Bovendien is er nummer 10 in de andere array. 9 en 82 sorteren als 9 82. Aldus combineert en levert deze array en array met waarde 10 9 en 82.
Tenslotte combineren 3 27 38 43 en 9 10 82 om de gesorteerde array te leveren.
Verschil tussen Quicksort en samenvoegsortering
Definitie
QuickSort is een efficiënt sorteeralgoritme dat dient als een systematische methode om de elementen van een array op orde te brengen. In tegenstelling hiermee is samenvoegsortering een efficiënte sorteeralgoritme op basis van algemene doeleinden, op basis van vergelijkingen. Dit is dus het fundamentele verschil tussen quicksort en samenvoegsortering.
functionaliteit
Bovendien is de functionaliteit het belangrijkste verschil tussen quicksort en samenvoegsortering. Quicksort sorteert de elementen door elk element met het draaipunt te vergelijken, terwijl samenvoegselectie de array keer op keer verdeelt in twee subarrays (n / 2) totdat een element overblijft.
Toepassing
Hoewel quicksort geschikt is voor kleine arrays, is samenvoeg sorteren ook geschikt voor elk type array.
Snelheid
Een ander verschil tussen quicksort en samenvoegsortering is dat de quicksort sneller werkt voor kleine gegevenssets, terwijl samenvoegsortering in constante snelheid werkt voor alle gegevenssets.
Ruimtevereiste
Bovendien is de benodigde ruimte ook een belangrijk verschil tussen quicksort en samenvoegsortering. Quicksort vereist een minimum aan ruimte in vergelijking met merge sort.
rendement
Bovendien is quicksort niet efficiënt voor grote arrays, maar samenvoegen is efficiënter dan quicksort. Dit is dus een ander verschil tussen quicksort en samenvoegsortering.
Conclusie
Samenvattend, het belangrijkste verschil tussen quicksort en samenvoegsortering is dat de quicksort de elementen sorteert door elk element te vergelijken met een element dat een spil wordt genoemd, terwijl de samenvoegselectie de array steeds opnieuw verdeelt in twee subarrays totdat een element overblijft.
Referentie:
1. Quicksort-algoritme | Deel 2, Onderwijs 4u, 15 maart 2018, hier beschikbaar.
2. Samenvoegen sorteren Voorbeeld, Onderwijs 4u, 15 maart 2018, hier beschikbaar.
Afbeelding met dank aan:
1. "Quicksort-diagram" door Znupi - Eigen werk (publiek domein) via Commons Wikimedia
2. "Merge sort algoritme diagram" door Vineet Kumar op Engelse Wikipedia - Overgebracht van en.wikipedia naar Commons door Eric Bauman met behulp van CommonsHelper (Public Domain) via Commons Wikimedia
