Beide Sortiertechniken, die schnelle Sortierung und die Mischsortierung, basieren auf der Divide-and-Conquer-Methode, bei der die Menge der Elemente getrennt und anschließend nach der Neuanordnung kombiniert wird. Die schnelle Sortierung erfordert normalerweise mehr Vergleiche als die Sortierreihenfolge zum Sortieren einer großen Menge von Elementen.
Vergleichstabelle
| Basis zum Vergleich | Schnelle Sorte | Zusammenführen, sortieren |
|---|---|---|
| Partitionierung der Elemente im Array | Die Aufteilung einer Liste von Elementen ist nicht notwendigerweise in zwei Hälften geteilt. | Das Array ist immer in die Hälfte (n / 2) unterteilt. |
| Worst-Case-Komplexität | O (n2) | O (n log n) |
| Funktioniert gut auf | Kleineres Array | Funktioniert in jeder Art von Array. |
| Geschwindigkeit | Schneller als andere Sortieralgorithmen für kleine Datensätze. | Gleichbleibende Geschwindigkeit in allen Arten von Datensätzen. |
| Zusätzlicher Speicherplatzbedarf | Weniger | Mehr |
| Effizienz | Ineffizient für größere Arrays. | Effizienter. |
| Sortiermethode | Intern | Externe |
Definition von Schnellsortierung
Die schnelle Sortierung ist ein durchgängig verwendeter Sortieralgorithmus, da er für kurze Arrays schnell ist. Die Menge der Elemente wird wiederholt in Teile aufgeteilt, bis eine weitere Unterteilung nicht möglich ist. Schnelle Sortierung wird auch als Partitionsaustausch Sortierung bezeichnet . Es verwendet ein Schlüsselelement (bekannt als Pivot) zur Unterteilung der Elemente. Eine Partition enthält die Elemente, die kleiner als das Schlüsselelement sind. Eine andere Partition enthält die Elemente, die größer als das Schlüsselelement sind. Die Elemente werden rekursiv sortiert.
Angenommen, A ist ein Array A [1], A [2], A [3], ..., A [n] von n Zahl, die sortiert werden müssen. Der Schnellsortieralgorithmus bestand aus den folgenden Schritten.
- Das erste Element oder ein beliebiges zufälliges Element, das als Schlüssel ausgewählt wurde, nimmt key = A (1) an.
- Der Zeiger "low" wird am zweiten und der Zeiger "up" am letzten Element des Arrays positioniert, dh low = 2 und up = n;
- Inkrementieren Sie den Zeiger "low" um eine Position bis (A [low]> Taste).
- Dekrementieren Sie den Aufwärtszeiger ständig um eine Position bis (A [Aufwärts] <= Taste).
- Wenn up größer als niedrig ist, wechseln Sie A [low] mit A [up].
- Wiederholen Sie die Schritte 3, 4 und 5, bis die Bedingung in Schritt 5 ausfällt (dh up <= low) und wechseln Sie dann A [up] mit der Taste.
- Wenn die Elemente links vom Schlüssel kleiner als der Schlüssel sind und die Elemente rechts vom Schlüssel größer als der Schlüssel sind, wird das Array in zwei Unterarrays unterteilt.
- Das obige Verfahren wird wiederholt auf die Subarrays angewendet, bis das gesamte Array sortiert ist.
Vorteile und Nachteile
Es besitzt ein gutes durchschnittliches Fallverhalten. Die Laufzeitkomplexität der schnellen Sortierung ist gut, dh sie ist schneller als Algorithmen wie Blasensortierung, Einfügungssortierung und Auswahlsortierung. Es ist jedoch komplex und sehr rekursiv, weshalb es nicht für große Arrays geeignet ist.
Definition von Merge Sort
Merge Sort ist ein externer Algorithmus, der ebenfalls auf der Divide and Conquer-Strategie basiert. Die Elemente werden immer wieder in Unterarrays (n / 2) aufgeteilt, bis nur noch ein Element übrig ist, was die Sortierzeit erheblich verkürzt. Es verwendet zusätzlichen Speicher zum Speichern des Hilfsarrays. Bei der Zusammenführungssortierung werden drei Arrays verwendet, in denen jeweils zwei Hälften gespeichert werden, und das dritte wird zum Speichern der endgültigen sortierten Liste verwendet. Jedes Array wird dann rekursiv sortiert. Zum Schluss werden die Subarrays zusammengefügt, um die Elementgröße des Arrays festzulegen. Die Liste ist immer in nur die Hälfte (n / 2) unterteilt und unterscheidet sich nicht von der schnellen Sortierung.
Sei A das Array aus n zu sortierenden Elementen A [1], A [2], ………, A [n]. Die Zusammenführungssortierung folgt den angegebenen Schritten.
- Teilen Sie das Array A in ungefähr n / 2 sortiertes Subarray um 2, was bedeutet, dass die Elemente in (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) Unterfelder müssen in sortierter Reihenfolge sein.
- Kombinieren Sie jedes Paar von Paaren, um die Liste der sortierten Subarrays der Größe 4 zu erhalten. Die Elemente in den Subarrays sind ebenfalls in sortierter Reihenfolge (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]).
- Der Schritt 2 wird wiederholt ausgeführt, bis es nur ein sortiertes Array der Größe n gibt.
Vorteile und Nachteile
Der Merge-Sortieralgorithmus arbeitet auf die gleiche und genaue Weise unabhängig von der Anzahl der an der Sortierung beteiligten Elemente. Es funktioniert auch mit dem großen Datensatz gut. Es verbraucht jedoch einen größeren Teil des Speichers.
Hauptunterschiede zwischen Schnellsortierung und Zusammenführungssortierung
- Bei der Zusammenführungssorte muss das Array nur in zwei Hälften (dh n / 2) unterteilt sein. Bei der schnellen Sortierung gibt es keinen Zwang, die Liste in gleiche Elemente zu unterteilen.
- Die Worst-Case-Komplexität der schnellen Sortierung ist O (n2), da im schlechtesten Zustand viel mehr Vergleiche erforderlich sind. Im Gegensatz dazu hat die Zusammenführungssortierung die gleichen Worst-Case- und Durchschnitts-Komplexitäten, d. H. O (n log n).
- Die Zusammenführungssortierung eignet sich für alle Arten von Datensätzen, egal ob groß oder klein. Im Gegensatz dazu kann die schnelle Sortierung nicht mit großen Datensätzen funktionieren.
- Die schnelle Sortierung ist in einigen Fällen schneller als die Zusammenführungssortierung, beispielsweise für kleine Datensätze.
- Mergesort erfordert zusätzlichen Speicherplatz zum Speichern der Hilfsarrays. Auf der anderen Seite erfordert die schnelle Sortierung nicht viel Platz für zusätzlichen Speicherplatz.
- Mergesort ist effizienter als schnelles Sortieren.
- Die schnelle Sortierung ist eine interne Sortiermethode, bei der die zu sortierenden Daten jeweils im Hauptspeicher abgeglichen werden. Umgekehrt ist die Zusammenführungssortierung eine externe Sortiermethode, bei der die zu sortierenden Daten nicht gleichzeitig im Speicher untergebracht werden können und einige im Hilfsspeicher aufbewahrt werden müssen.
Fazit
Die schnelle Sortierung ist schnellere Fälle, ist jedoch in einigen Situationen ineffizient und führt im Vergleich zur Zusammenführungssortierung viele Vergleiche durch. Obwohl die Zusammenführungssortierung weniger Vergleich erfordert, benötigt sie einen zusätzlichen Speicherplatz von 0 (n) zum Speichern des zusätzlichen Arrays, während die Schnellsortierung Speicherplatz von O (log n) erfordert.
