Inhalt

• Vergleichstabelle
• Definition von Schnellsortierung
• Definition der Zusammenführungssortierung
• Fazit

Die Sortieralgorithmen für schnelles Sortieren und Zusammenführen basieren auf dem Divisions- und Eroberungsalgorithmus, der auf ganz ähnliche Weise funktioniert. Der vorherige Unterschied zwischen der Schnell- und der Zusammenführungssortierung besteht darin, dass bei der Schnellsortierung das Drehelement für die Sortierung verwendet wird. Beim Sortieren zusammenführen wird hingegen kein Pivot-Element zum Durchführen der Sortierung verwendet.

Beide Sortiertechniken, schnelles Sortieren und Zusammenführen, basieren auf der Divide-and-Conquer-Methode, bei der die Elemente getrennt und nach der Neuanordnung kombiniert werden. Die schnelle Sortierung erfordert normalerweise mehr Vergleiche als die Sortierung durch Zusammenführen, um eine große Menge von Elementen zu sortieren.

1. 1. Vergleichstabelle
   2. Definition
   3. Hauptunterschiede
   4. Fazit

Vergleichstabelle

Vergleichsbasis	Schnelle Sorte	Zusammenführen, sortieren
Partitionierung der Elemente im Array	Das Teilen einer Liste von Elementen ist nicht notwendigerweise in zwei Hälften unterteilt.	Array wird immer in zwei Hälften geteilt (n / 2).
Komplexität im schlimmsten Fall	Auf2)	O (n log n)
Funktioniert gut auf	Kleineres Array	Funktioniert gut in jeder Art von Array.
Geschwindigkeit	Schneller als andere Sortieralgorithmen für kleine Datenmengen.	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

Schnelle Sorte ist ein weit verbreiteter Sortieralgorithmus, da er für kurze Arrays schnell ist. Die Menge der Elemente wird so oft in Teile geteilt, bis eine weitere Aufteilung nicht mehr möglich ist. Schnelle Sortierung ist auch bekannt als Partition Exchange sortieren. Es verwendet ein Schlüsselelement (bekannt als Pivot) zum Unterteilen 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, A, A, ..., A mit n Zahlen, die sortiert werden müssen. Der schnelle Sortieralgorithmus umfasst die folgenden Schritte.

1. Das erste Element oder ein beliebiges zufälliges Element, das als Schlüssel ausgewählt wurde, wird als Schlüssel = A (1) angenommen.
2. Der "niedrige" Zeiger befindet sich am zweiten und der "obere" Zeiger am letzten Element des Arrays, d. H. Niedrig = 2 und hoch = n;
3. Erhöhen Sie den "niedrigen" Zeiger konsequent um eine Position, bis (A> -Taste).
4. Verringern Sie den Aufwärtszeiger ständig um eine Position, bis (A <= Taste).
5. Wenn up größer als low ist, tausche A mit A.
6. Wiederholen Sie die Schritte 3, 4 und 5, bis die Bedingung in Schritt 5 nicht mehr erfüllt ist (d. H. Auf <= niedrig), und tauschen Sie dann A mit der Taste aus.
7. 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.
8. 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, das heißt, sie ist schneller als Algorithmen wie Bubble-Sortierung, Einfügesortierung und Auswahlsortierung. Es ist jedoch komplex und sehr rekursiv, weshalb es nicht für große Arrays geeignet ist.

Definition der Zusammenführungssortierung

Zusammenführen, sortieren ist ein externer Algorithmus, der ebenfalls auf der Divide- und Conquer-Strategie basiert. Die Elemente werden immer wieder in Unterfelder (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. Die Zusammenführungssortierung verwendet drei Arrays, von denen zwei zum Speichern jeder Hälfte und die dritte zum Speichern der endgültigen sortierten Liste verwendet werden. Jedes Array wird dann rekursiv sortiert. Zuletzt werden die Subarrays zusammengeführt, um die Elementgröße des Arrays zu bestimmen. Die Liste ist immer in nur die Hälfte (n / 2) unterteilt, die sich von der schnellen Sortierung unterscheidet.

Sei A das Array von n zu sortierenden Elementen A, A, ………, A. Die Zusammenführungssortierung folgt den angegebenen Schritten.

1. Teilen Sie das Array A in ungefähr n / 2 sortierte Unterarrays durch 2 auf, was bedeutet, dass die Elemente in den Unterarrays (A, A), (A, A), (A, A), (A, A) müssen in sortierter Reihenfolge sein.
2. Kombinieren Sie jedes Paar von Paaren, um die Liste der sortierten Subarrays der Größe 4 zu erhalten. Die Elemente in den Unterfeldern sind auch in sortierter Reihenfolge (A, A, A, A), ..., (A, A, A, A), ..., (A, A, A, A).
3. Der Schritt 2 wird wiederholt ausgeführt, bis es nur noch ein sortiertes Array der Größe n gibt.

   

Vorteile und Nachteile

Der Algorithmus für die Zusammenführungssortierung wird unabhängig von der Anzahl der Elemente, die an der Sortierung beteiligt sind, auf exakt dieselbe und präzise Weise ausgeführt. Es funktioniert auch mit dem großen Datensatz. Es verbraucht jedoch einen größeren Teil des Speichers.

1. Bei der Zusammenführungssortierung muss das Array in nur zwei Hälften aufgeteilt werden (d. H. N / 2). Im Gegensatz dazu besteht bei der schnellen Sortierung kein Zwang, die Liste in gleiche Elemente zu unterteilen.
2. Die Komplexität der schnellen Sortierung im schlimmsten Fall ist O (n²), da es im schlechtesten Zustand viel mehr Vergleiche erfordert. Im Gegensatz dazu haben Zusammenführungssortierungen die gleichen Komplexitäten für den schlimmsten und den durchschnittlichen Fall, dh O (n log n).
3. Die Zusammenführungssortierung kann für alle Arten von Datensätzen verwendet werden, unabhängig davon, ob sie groß oder klein sind. Im Gegenteil, die schnelle Sortierung kann mit großen Datenmengen nicht gut funktionieren.
4. Schnelles Sortieren ist in einigen Fällen schneller als Sortieren durch Zusammenführen, z. B. bei kleinen Datenmengen.
5. Für das Zusammenführen von Sortierungen wird zusätzlicher Speicherplatz zum Speichern der Hilfsarrays benötigt. Andererseits benötigt die schnelle Sortierung nicht viel Platz für zusätzlichen Speicher.
6. Sortieren zusammenführen ist effizienter als schnelles Sortieren.
7. Die schnelle Sortierung ist eine interne Sortierungsmethode, bei der die zu sortierenden Daten zu einem Zeitpunkt im Hauptspeicher angepasst 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

Bei der schnellen Sortierung handelt es sich um schnellere Fälle, die jedoch in einigen Situationen ineffizient sind. Außerdem werden im Vergleich zur Sortierung durch Zusammenführen viele Vergleiche durchgeführt. Obwohl für das Sortieren beim Zusammenführen weniger Vergleiche erforderlich sind, wird für das Speichern des zusätzlichen Arrays ein zusätzlicher Speicherplatz von 0 (n) benötigt, während für das schnelle Sortieren ein Speicherplatz von 0 (log n) benötigt wird.