In dit artikel zullen we belangrijke eigenschappen van verschillende sorteertechnieken bespreken, waaronder hun complexiteit, stabiliteit en geheugenbeperkingen. Voordat u dit artikel begrijpt, moet u de basisprincipes van verschillende sorteertechnieken begrijpen (Zie : Sorteertechnieken).
Tijdcomplexiteitsanalyse –
We hebben de beste, gemiddelde en slechtste complexiteit van verschillende sorteertechnieken besproken met mogelijke scenario’s.
Sorteren op basis van vergelijking –
In sorteren op basis van vergelijking worden elementen van een array met elkaar vergeleken om de gesorteerde array te vinden.
- Bubble sort en Insertion sort –
Gemiddelde en worst-case tijdcomplexiteit: n^2
Best-case tijdcomplexiteit: n als array al gesorteerd is.
Worst case: wanneer de array omgekeerd gesorteerd is. - Selection sort –
Best, average and worst case time complexity: n^2 die onafhankelijk is van de verdeling van de data. - Merge sort –
Beste, gemiddelde en slechtste tijdscomplexiteit: nlogn die onafhankelijk is van de verdeling van de gegevens. - Heap sort –
Beste, gemiddelde en slechtste tijdscomplexiteit: nlogn die onafhankelijk is van de verdeling van de gegevens. - Quick sort –
Het is een verdeel-en-heers-benadering met recurrensierelatie:T(n) = T(k) + T(n-k-1) + cn
In het slechtste geval: wanneer de array is gesorteerd of omgekeerd gesorteerd, verdeelt het verdeelalgoritme de array in twee subarrays met 0 en n-1 elementen. Daarom
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Best case en Average case: Gemiddeld verdeelt het partitiealgoritme de matrix in twee deelmatrices van gelijke grootte. Daarom
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Sorteren zonder vergelijking –
In sorteren zonder vergelijking worden de elementen van de matrix niet met elkaar vergeleken om de gesorteerde matrix te vinden.
- Radix sort –
Beste, gemiddelde en slechtste tijdcomplexiteit: nk waarbij k het maximum aantal cijfers in elementen van array is. - Count sort –
Beste, gemiddelde en slechtste tijdcomplexiteit: n+k waarbij k de grootte van count array is. - Bucket sort –
Beste en gemiddelde tijdcomplexiteit: n+k waarbij k het aantal buckets is.
Slechtste tijdcomplexiteit: n^2 als alle elementen tot dezelfde bucket behoren.
In-place/Outplace techniek –
Een sorteertechniek is inplace als deze geen extra geheugen gebruikt om de array te sorteren.
Van de besproken technieken op basis van vergelijking is alleen merge sort een outplaced-techniek, omdat er een extra array nodig is om de gesorteerde subarrays samen te voegen.
Van de besproken technieken op basis van niet-vergelijking zijn alle outplaced-technieken. Counting sort gebruikt een tel-array en bucket sort gebruikt een hash-tabel voor het sorteren van de array.
Online/Offline techniek –
Een sorteertechniek wordt als Online beschouwd als deze nieuwe gegevens kan accepteren terwijl de procedure loopt, d.w.z. dat er geen volledige gegevens nodig zijn om de sorteerbewerking te starten.
Van de besproken technieken die op vergelijking zijn gebaseerd, komt alleen Insertion Sort hiervoor in aanmerking vanwege het onderliggende algoritme dat het gebruikt, d.w.z. het verwerkt de array (niet alleen elementen) van links naar rechts en als nieuwe elementen rechts worden toegevoegd, heeft dat geen invloed op de lopende bewerking.
Stabiele/onstabiele techniek –
Een sorteertechniek is stabiel als deze de volgorde van elementen met dezelfde waarde niet wijzigt.
Van de technieken die op vergelijking zijn gebaseerd, zijn bubble sort, insertion sort en merge sort stabiele technieken. Selection sort is onstabiel omdat het de volgorde van elementen met dezelfde waarde kan veranderen. Bijvoorbeeld, beschouw de array 4, 4, 1, 3.
In de eerste iteratie, het minimum element gevonden is 1 en het wordt verwisseld met 4 op de 0e positie. Daarom zal de volgorde van 4 ten opzichte van 4 op de 1e positie veranderen. Op dezelfde manier zijn ook quick sort en heap sort onstabiel.
Van de niet-vergelijkende technieken zijn Counting sort en Bucket sort stabiele sorteertechnieken, terwijl de stabiliteit van radix sort afhangt van het onderliggende algoritme dat voor het sorteren wordt gebruikt.
Analyse van sorteertechnieken :
- Wanneer de array bijna gesorteerd is, kan insertion sort de voorkeur krijgen.
- Wanneer de volgorde van invoer niet bekend is, heeft merge sort de voorkeur omdat het in het slechtste geval een tijdcomplexiteit van nlogn heeft en het is ook stabiel.
- Wanneer de array gesorteerd is, geeft insertion en bubble sort een complexiteit van n maar quick sort geeft een complexiteit van n^2.
Que – 1. Welk sorteeralgoritme neemt de minste tijd in beslag als alle elementen van de input array identiek zijn? Beschouw typische implementaties van sorteeralgoritmen.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
Oplossing: Zoals besproken, zal insertion sort de complexiteit van n hebben als de input array al gesorteerd is.
Que – 2. Beschouw het Quicksort-algoritme. Stel dat er een procedure is voor het vinden van een pivot-element die de lijst in twee deellijsten splitst die elk ten minste een vijfde van de elementen bevatten. Zij T(n) het aantal vergelijkingen dat nodig is om n elementen te sorteren. Dan geldt (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Oplossing: De complexiteit van quick sort kan geschreven worden als:
T(n) = T(k) + T(n-k-1) + cn
Zoals gegeven in de vraag, bevat een lijst 1/5e van het totaal aantal elementen. Daarom zal een andere lijst 4/5 van het totaal aantal elementen bevatten. Als we de waarden omrekenen, krijgen we:
T(n) = T(n/5) + T(4n/5) + cn, wat overeenkomt met optie (B).
Vergelijkingstabel van tijd- en ruimtecomplexiteit :
| Sorteeralgoritme | Tijdcomplexiteit | Ruimtecomplexiteit | ||
|---|---|---|---|---|
| Beste geval | Gemiddelde Case | Worst Case | Worst Case | |
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Selectie sorteren | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Insortering sorteren | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Quick Sort | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
