Beide sorteertechnieken, snel sorteren en samenvoegen sorteren zijn gebaseerd op de verdeel en heers methode waarbij de set elementen wordt gescheiden en vervolgens na herrangschikking wordt gecombineerd. De snelle sortering vereist meestal meer vergelijkingen dan merge sortering voor het sorteren van een groot aantal elementen.
Vergelijkingstabel
| Basis voor vergelijking | Snel sorteren | Sortering samenvoegen |
|---|---|---|
| Partitionering van de elementen in de array | Het splitsen van een lijst met elementen is niet noodzakelijkerwijs in tweeën verdeeld. | Array is altijd verdeeld in de helft (n / 2). |
| Complexiteit van het ergste geval | O (n2) | O (n log n) |
| Werkt goed | Kleinere array | Werkt prima in elk type array. |
| Snelheid | Sneller dan andere sorteeralgoritmen voor kleine gegevensverzamelingen. | Consistente snelheid in alle soorten gegevenssets. |
| Extra vereiste opslagruimte | Minder | Meer |
| rendement | Inefficiënt voor grotere matrices. | Efficiënter. |
| Sorteermethode | intern | extern |
Definitie van snel sorteren
Snel sorteren is een wijdverbreid sorteeralgoritme omdat het snel is voor de korte arrays. De verzameling elementen wordt herhaaldelijk verdeeld in delen totdat het niet mogelijk is deze verder te verdelen. Snel sorteren wordt ook wel Partition Exchange-sortering genoemd . Het gebruikt een sleutelelement (bekend als de spil) voor het partitioneren van de elementen. Eén partitie bevat die elementen die kleiner zijn dan het sleutelelement. Een andere partitie bevat die elementen die groter zijn dan het sleutelelement. De elementen worden recursief gesorteerd.
Stel dat A een array A [1], A [2], A [3], ...... .., A [n] van n-nummer is die moet worden gesorteerd. Het quick sort-algoritme bestaat uit de volgende stappen.
- Het eerste element of willekeurig element geselecteerd als de sleutel, neem de sleutel = A (1).
- De "lage" aanwijzer wordt geplaatst bij de tweede en de "omhoog" -aanwijzer wordt geplaatst bij het laatste element van de array, dwz laag = 2 en hoger = n;
- Consequent, verhoogt u de "lage" wijzer met één positie tot (een [lage]> toets).
- Verlaag constant de "omhoog" -aanwijzer met één positie tot (A [omhoog] <= toets).
- Als hoger groter is dan laag wisselpunt A [laag] met A [omhoog].
- Herhaal stap 3, 4 en 5 totdat de toestand in stap 5 mislukt (dus <= laag) en wissel dan A [omhoog] met de sleutel.
- Als de elementen links van de sleutel kleiner zijn dan de sleutel en de elementen rechts van de sleutel groter zijn dan de sleutel, wordt de array opgedeeld in twee subarrays.
- De bovenstaande procedure wordt herhaaldelijk toegepast op de subreeksen totdat de volledige array is gesorteerd.
Voor-en nadelen
Het heeft een goed gemiddeld gedrag van de zaak. De rijtijdcomplexiteit van de snelle sortering is goed, want deze is sneller dan algoritmen zoals bellen sorteren, invoegtypen en selectie sorteren. Het is echter complex en zeer recursief, daarom is het niet geschikt voor grote arrays.
Definitie van samenvoegsortering
Samenvoegsortering is een extern algoritme dat ook gebaseerd is op een verdeel- en heersstrategie. De elementen worden keer op keer gesplitst in sub-arrays (n / 2) totdat slechts één element over is, wat de sorteringstijd aanzienlijk verkort. Het gebruikt extra opslagruimte voor het opslaan van de hulparray. Samenvoegsortering maakt gebruik van drie matrices waar twee worden gebruikt voor het opslaan van elke helft en de derde wordt gebruikt om de uiteindelijke gesorteerde lijst op te slaan. Elke array wordt vervolgens recursief gesorteerd. Eindelijk worden de subarrays samengevoegd om het tot een elementgrootte van de array te maken. De lijst is altijd verdeeld in slechts de helft (n / 2), anders dan snel sorteren.
Laat A de reeks van n aantal te sorteren elementen zijn A [1], A [2], ..., A [n]. De samenvoegsoort volgt de gegeven stappen.
- Splits de array A in ongeveer n / 2 gesorteerde subarray met 2, wat betekent dat de elementen in de (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) sub-arrays moeten in gesorteerde volgorde zijn.
- Combineer elk paar paren om de lijst met gesorteerde subreeksen van maat 4 te krijgen; de elementen in de subarrays zijn ook in gesorteerde volgorde, (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]).
- De stap 2 wordt herhaald uitgevoerd totdat er slechts één gesorteerde array van grootte n is.
Voor-en nadelen
Het samenvoegsorteeralgoritme voert exact dezelfde en nauwkeurige manier uit, ongeacht het aantal elementen dat bij het sorteren is betrokken. Het werkt prima, zelfs met de grote gegevensset. Het verbruikt echter een groter deel van het geheugen.
Belangrijkste verschillen tussen snel sorteren en samenvoegen sorteren
- Bij de samenvoegsortering moet de array in slechts twee helften worden verdeeld (dus n / 2). Tegen, in snel soort, is er geen dwang om de lijst in gelijke elementen te verdelen.
- De ergste case-complexiteit van snel sorteren is O (n2) omdat het veel meer vergelijkingen vergt in de slechtste omstandigheden. In tegenstelling hebben samenvoegsoorten dezelfde worst case en gemiddelde case complexiteiten, dat is O (n log n).
- Samenvoegen sorteren kan goed werken op elk type gegevenssets, of het nu groot of klein is. Integendeel, het snel sorteren kan niet goed werken met grote datasets.
- Snel sorteren is sneller dan samenvoegen in sommige gevallen, bijvoorbeeld voor kleine gegevenssets.
- Samenvoegen sortering vereist extra geheugenruimte om de hulparrays op te slaan. Aan de andere kant vereist de snelle sortering niet veel ruimte voor extra opslag.
- Samenvoegen sorteren is efficiënter dan snel sorteren.
- De snelle sortering is een interne sorteermethode waarbij de gegevens die moeten worden gesorteerd, tegelijkertijd in het hoofdgeheugen worden aangepast. Omgekeerd is de merge-sortering een externe sorteermethode waarbij de gegevens die moeten worden gesorteerd niet tegelijkertijd in het geheugen kunnen worden ondergebracht en sommige in het hulpgeheugen moeten worden bewaard.
Conclusie
De snelle sortering is sneller, maar is in sommige situaties inefficiënt en voert ook veel vergelijkingen uit in vergelijking met merge sort. Hoewel merge sorting minder vergelijking vereist, heeft het een extra geheugenruimte van 0 (n) nodig om de extra array op te slaan, terwijl voor snel sorteren ruimte O (log n) nodig is.
