Verschil tussen Snel sorteren en Samenvoegen sorteren
Inhoud
De snelle sorteer- en samenvoegsorteeralgoritmen zijn gebaseerd op het verdeel en heers algoritme dat op dezelfde manier werkt. Het eerdere verschil tussen de quick- en merge-sortering is dat bij quick-sortering het pivot-element wordt gebruikt voor het sorteren. Aan de andere kant gebruikt het samenvoegen sorteren geen pivot-element voor het uitvoeren van het sorteren.
Beide sorteertechnieken, quick sort en merge sort zijn gebouwd op de verdeel en heers methode waarbij de set elementen worden gescheiden en vervolgens worden gecombineerd na herschikking. Het snelle sorteren vereist meestal meer vergelijkingen dan het samenvoegen voor het sorteren van een groot aantal elementen.
-
- Vergelijkingstabel
- Definitie
- Belangrijkste verschillen
- Gevolgtrekking
Vergelijkingstabel
| Basis voor vergelijking | Snel sorteren | Sorteer samenvoegen |
|---|---|---|
| Partitionering van de elementen in de array | Het splitsen van een lijst met elementen is niet noodzakelijkerwijs in tweeën gedeeld. | Matrix is altijd in tweeën gedeeld (n / 2). |
| De complexiteit van het ergste geval | Aan2) | O (n log n) |
| Werkt goed op | Kleinere reeks | Werkt prima in elk type array. |
| Snelheid | Sneller dan andere sorteeralgoritmen voor kleine gegevensverzamelingen. | Consistente snelheid in alle soorten gegevenssets. |
| Extra opslagruimte vereist | Minder | Meer |
| rendement | Inefficiënt voor grotere arrays. | Efficiënter. |
| Sorteermethode | intern | extern |
Definitie van snel sorteren
Snel sorteren is alomtegenwoordig gebruikt sorteeralgoritme omdat het snel is voor de korte arrays. De verzameling elementen wordt herhaaldelijk in delen verdeeld totdat het niet meer mogelijk is deze verder te verdelen. Snel sorteren is ook bekend als partitie uitwisseling soort. Het gebruikt een sleutelelement (bekend als de pivot) 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, A, A, ... ..., A van n nummer is die moet worden gesorteerd. Het snelle sorteeralgoritme bestaat uit de volgende stappen.
- Het eerste element of een willekeurig element dat als sleutel is geselecteerd, neemt aan dat sleutel = A (1).
- De "lage" wijzer wordt op de tweede geplaatst en de "bovenste" wijzer wordt op het laatste element van de array geplaatst, d.w.z. low = 2 en up = n;
- Verhoog consequent de "lage" aanwijzer met één positie tot (A> toets).
- Verlaag de aanwijzer "omhoog" constant met één positie tot (A <= toets).
- Als up groter is dan laag wissel A met A.
- Herhaal stap 3,4 en 5 totdat de voorwaarde in stap 5 mislukt (d.w.z. omhoog <= laag) en wissel vervolgens A in 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 verdeeld in twee subarrays.
- De bovenstaande procedure wordt herhaaldelijk toegepast op de subreeksen totdat de hele array is gesorteerd.
Voor-en nadelen
Het bezit een goed gemiddeld casusgedrag. De doorlooptijdcomplexiteit van de snelle sortering is goed, dat wil zeggen dat deze sneller is dan algoritmen zoals bubbelsortering, invoegsortering en selectiesortering. Het is echter complex en zeer recursief, dat is de reden dat het niet geschikt is voor grote reeksen.
Definitie van samenvoegsortering
Sorteer samenvoegen is een extern algoritme dat ook gebaseerd is op verdeel en heers strategie. De elementen worden telkens in sub-reeksen (n / 2) gesplitst totdat er nog maar één element over is, wat de sorteertijd aanzienlijk verkort. Het gebruikt extra opslag voor het opslaan van de hulparray. Het samenvoegen sorteert drie arrays waarbij twee worden gebruikt voor het opslaan van elke helft en de derde wordt gebruikt om de laatste gesorteerde lijst op te slaan. Elke array wordt vervolgens recursief gesorteerd. Eindelijk worden de subreeksen samengevoegd om er een elementgrootte van de array van te maken. De lijst is altijd onderverdeeld in slechts de helft (n / 2) die niet overeenkomt met snel sorteren.
Laat A de array zijn van n aantal te sorteren elementen A, A, ………, A. De samenvoegsortering volgt de gegeven stappen.
- Splits de array A in ongeveer n / 2 gesorteerde subarray door 2, wat betekent dat de elementen in de (A, A), (A, A), (A, A), (A, A) subarrays moeten in gesorteerde volgorde zijn.
- Combineer elk paar paren om de lijst met gesorteerde subreeksen van maat 4 te verkrijgen; de elementen in de subreeksen staan ook in gesorteerde volgorde, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
- De stap 2 wordt herhaaldelijk uitgevoerd totdat er slechts één gesorteerde reeks van grootte n is.
Voor-en nadelen
Het samenvoeg-sorteeralgoritme werkt op exact dezelfde en precieze manier, ongeacht het aantal elementen dat bij het sorteren is betrokken. Het werkt prima, zelfs met de grote dataset. Het verbruikt echter een groter deel van het geheugen.
- Bij het samenvoegen moet de array in slechts twee helften worden gescheiden (d.w.z. n / 2). In tegenstelling, in snel soort, is er geen verplichting om de lijst in gelijke elementen te verdelen.
- De worst case complexiteit van quick sort is O (n2) omdat er in de slechtste toestand veel meer vergelijkingen nodig zijn. Fusiesorteringen hebben daarentegen dezelfde worst case en gemiddelde case complexiteiten, dat wil zeggen O (n log n).
- Het samenvoegen kan goed werken op elk type gegevensset, of deze nu groot of klein is. Integendeel, de snelle sortering kan niet goed werken met grote datasets.
- Snel sorteren is sneller dan samenvoegen sorteren in sommige gevallen, zoals voor kleine gegevenssets.
- Voor het samenvoegen is extra geheugenruimte vereist om de hulparrays op te slaan. Aan de andere kant vereist de snelle sortering niet veel ruimte voor extra opslag.
- Sorteren samenvoegen is efficiënter dan snel sorteren.
- De snelle sortering is een interne sorteermethode waarbij de te sorteren gegevens tegelijkertijd in het hoofdgeheugen worden aangepast. Omgekeerd is de merge-sortering een externe sorteermethode waarbij de te sorteren gegevens niet tegelijkertijd in het geheugen kunnen worden ondergebracht en sommige in het hulpgeheugen moeten worden bewaard.
Gevolgtrekking
De snelle sortering is snellere gevallen, maar is in sommige situaties inefficiënt en voert ook veel vergelijkingen uit in vergelijking met het samenvoegen. Hoewel samenvoegen sorteren minder vergelijking vereist, heeft het een extra geheugenruimte van 0 (n) nodig voor het opslaan van de extra array, terwijl snel sorteren ruimte van O (log n) nodig heeft.
