In diesem Artikel werden wir wichtige Eigenschaften verschiedener Sortierverfahren besprechen, einschließlich ihrer Komplexität, Stabilität und Speicherbeschränkungen. Bevor Sie diesen Artikel verstehen, sollten Sie die Grundlagen verschiedener Sortiertechniken verstehen (siehe: Sortiertechniken).
Analyse der Zeitkomplexität –
Wir haben die beste, durchschnittliche und schlimmste Komplexität verschiedener Sortiertechniken mit möglichen Szenarien diskutiert.
Vergleichssortierung –
Bei der Vergleichssortierung werden die Elemente eines Arrays miteinander verglichen, um das sortierte Array zu finden.
- Blasensortierung und Einfügesortierung –
Durchschnittliche und schlimmste Zeitkomplexität: n^2
Beste Zeitkomplexität: n, wenn das Array bereits sortiert ist.
Schlimmster Fall: wenn das Feld umgekehrt sortiert ist. - Auswahlsortierung –
Beste, durchschnittliche und schlimmste Zeitkomplexität: n^2, die unabhängig von der Verteilung der Daten ist. - Merge sort –
Beste, durchschnittliche und schlimmste Zeitkomplexität: nlogn, die unabhängig von der Verteilung der Daten ist. - Heap sort –
Beste, durchschnittliche und schlimmste Zeitkomplexität: nlogn, die unabhängig von der Verteilung der Daten ist. - Schnellsortierung –
Es handelt sich um einen Divide-and-Conquer-Ansatz mit Rekursionsbeziehung:T(n) = T(k) + T(n-k-1) + cn
Schlechtester Fall: Wenn das Array sortiert oder umgekehrt sortiert ist, teilt der Partitionsalgorithmus das Array in zwei Subarrays mit 0 und n-1 Elementen. Daher,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Bester Fall und Durchschnittlicher Fall: Im Durchschnitt unterteilt der Partitionsalgorithmus das Array in zwei gleich große Subarrays. Daher
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Sortierung ohne Vergleich –
Bei der Sortierung ohne Vergleich werden die Elemente der Anordnung nicht miteinander verglichen, um die sortierte Anordnung zu finden.
- Radix-Sortierung –
Beste, durchschnittliche und schlimmste Zeitkomplexität: nk, wobei k die maximale Anzahl von Ziffern in den Elementen des Arrays ist. - Zählsortierung –
Beste, durchschnittliche und schlimmste Zeitkomplexität: n+k, wobei k die Größe des Zählarrays ist. - Bucket sort –
Beste und durchschnittliche Zeitkomplexität: n+k, wobei k die Anzahl der Buckets ist.
Schlimmstenfalls Zeitkomplexität: n^2, wenn alle Elemente zum selben Bucket gehören.
In-place/Outplace-Technik –
Eine Sortiertechnik ist inplace, wenn sie keinen zusätzlichen Speicher zum Sortieren des Arrays verwendet.
Unter den besprochenen vergleichsbasierten Techniken ist nur die Merge-Sortierung eine Outplaced-Technik, da sie ein zusätzliches Array benötigt, um die sortierten Subarrays zusammenzuführen.
Unter den besprochenen nicht vergleichsbasierten Techniken sind alle Outplaced-Techniken. Bei der Zählsortierung wird ein Zählarray und bei der Eimersortierung eine Hashtabelle zum Sortieren des Arrays verwendet.
Online/Offline-Verfahren –
Ein Sortierverfahren gilt als online, wenn es neue Daten akzeptieren kann, während das Verfahren läuft, d.h. es werden keine vollständigen Daten benötigt, um den Sortiervorgang zu starten.
Unter den besprochenen vergleichsbasierten Verfahren qualifiziert sich nur Insertion Sort dafür aufgrund des zugrunde liegenden Algorithmus, den es verwendet, d.h. Sie verarbeitet das Array (nicht nur die Elemente) von links nach rechts, und wenn neue Elemente auf der rechten Seite hinzugefügt werden, wirkt sich das nicht auf die laufende Operation aus.
Stabiles/unstabiles Verfahren –
Ein Sortierverfahren ist stabil, wenn es die Reihenfolge von Elementen mit demselben Wert nicht ändert.
Unter den vergleichsbasierten Verfahren sind Bubble Sort, Insertion Sort und Merge Sort stabile Verfahren. Die Auswahlsortierung ist instabil, da sie die Reihenfolge von Elementen mit demselben Wert ändern kann. Betrachten wir zum Beispiel das Array 4, 4, 1, 3.
In der ersten Iteration ist das kleinste gefundene Element 1 und es wird mit 4 an der Position 0 vertauscht. Daher ändert sich die Reihenfolge von 4 in Bezug auf 4 an der Position 1. In ähnlicher Weise sind Quick Sort und Heap Sort ebenfalls instabil.
Von den nicht vergleichsbasierten Techniken sind Counting Sort und Bucket Sort stabile Sortiertechniken, während die Stabilität von Radix Sort von dem zugrunde liegenden Algorithmus abhängt, der für die Sortierung verwendet wird.
Analyse von Sortiertechniken :
- Wenn das Array fast sortiert ist, kann Insertion Sort bevorzugt werden.
- Wenn die Reihenfolge der Eingabe nicht bekannt ist, wird Merge Sort bevorzugt, da es im schlimmsten Fall eine Zeitkomplexität von nlogn hat und auch stabil ist.
- Wenn das Array sortiert ist, ergibt Insertion und Bubble Sort eine Komplexität von n, aber Quick Sort ergibt eine Komplexität von n^2.
Que – 1. Welcher Sortieralgorithmus benötigt am wenigsten Zeit, wenn alle Elemente des Eingabefeldes identisch sind? Betrachten Sie typische Implementierungen von Sortieralgorithmen.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
Lösung: Wie besprochen, hat Insertion Sort die Komplexität von n, wenn das Eingabefeld bereits sortiert ist.
Que – 2. Betrachten Sie den Quicksort-Algorithmus. Angenommen, es gibt ein Verfahren zum Finden eines Pivot-Elements, das die Liste in zwei Unterlisten aufteilt, von denen jede mindestens ein Fünftel der Elemente enthält. T(n) sei die Anzahl der Vergleiche, die erforderlich sind, um n Elemente zu sortieren. Dann ist (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
Lösung: Die Komplexität der schnellen Sortierung kann wie folgt geschrieben werden:
T(n) = T(k) + T(n-k-1) + cn
Wie in der Frage angegeben, enthält eine Liste 1/5 der gesamten Elemente. Daher wird eine andere Liste 4/5 der Gesamtelemente enthalten. Wenn man die Werte einsetzt, erhält man:
T(n) = T(n/5) + T(4n/5) + cn, was der Option (B) entspricht.
Zeit- und Raumkomplexitätsvergleichstabelle :
| Sortieralgorithmus | Zeitkomplexität | Raumkomplexität | ||
|---|---|---|---|---|
| Best Case | Average Fall | Schlechtester Fall | Schlechtester Fall | |
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Auswahlsortierung | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Einfügungssortierung | Ω(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) |
| Zählen Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
