Was ist der Unterschied zwischen Quicksort und Merge Sort

Das Hauptunterschied zwischen quicksort und merge sort ist das quicksort sortiert die Elemente durch Vergleichen jedes Elements mit einem Element, das als Drehpunkt bezeichnet wird, während Merge Sort das Array immer wieder in zwei Unterfelder unterteilt, bis ein Element übrig bleibt.

Sortieren ist die Methode, Daten in einer bestimmten Reihenfolge anzuordnen. Bei der Anordnung der Daten kann die numerische oder lexikografische Reihenfolge berücksichtigt werden. Durch das Sortieren können Datenelemente schneller und schneller gesucht und darauf zugegriffen werden. Es gibt verschiedene Sortieralgorithmen, und Quicksort und Merge Sort sind zwei davon.

Wichtige Bereiche

1. Was ist Quicksort?
     - Definition, Funktionalität
2. Was ist Mergesort?
     - Definition, Funktionalität
3. Was ist der Unterschied zwischen Quicksort und Merge Sort
     - Vergleich der wichtigsten Unterschiede

Schlüsselbegriffe

Algorithmus, Array, Sortierreihenfolge, Quicksort

Was ist Quicksort?

Quicksort ist ein interner Algorithmus, der die Divide and Conquer-Technik verwendet. Es heißt auch eine Partitionsaustauschart. Es verwendet ein Schlüsselelement namens Pivot, um die Elemente im Array zu vergleichen und zu partitionieren. Die Artikel mit einem geringeren Wert als der Drehpunkt werden auf die linke Seite des Drehpunkts gesetzt, während Artikel mit einem höheren Wert als der Drehpunkt auf die rechte Seite des Drehpunkts gelangen. Der linke Abschnitt wird als linke Partition bezeichnet, und der rechte Abschnitt wird als rechte Partition bezeichnet.

Abbildung 1: Quicksort

Siehe das unten stehende Beispiel.

36 34 43 11 15 20 28 45 27 32

Betrachten Sie 32 als Drehpunkt und betrachten Sie 36 und 27. Die Bedingungen 36 < pivot, 27 > Pivot sind falsch. Daher können wir diese beiden Werte vertauschen. Nun ist die Liste wie folgt.

27 34 43 11 15 20 28 45 36 32

Berücksichtigen Sie die Werte 34 und 45 < pivot, the condition is false. Similarly, 45 > Pivot-Bedingung ist wahr. Nun können wir von 45 auf 28 wechseln. Betrachten wir 34 und 28. 34 < pivot is false and 28 > Drehpunkt ist falsch. Daher können wir 34 und 28 tauschen.

27 28 43 11 15 20 34 45 36 32

Betrachten Sie 43 und 20. 43 < pivot is false. 20 > Drehpunkt ist falsch. Daher können wir die beiden Zahlen tauschen. Nun ist die Liste wie folgt.

27 28 20 11 15 43 34 45 36 32

Betrachten wir nun 11 und 15. 11 < pivot is true. We can consider 15. It is less than 32. It is the overlapping point, and we can place 32 as follows.

27 28 20 11 15 32 43 34 45 36 

Nun sind die Zahlen auf der linken Seite des Pivots kleiner als der Pivot und die rechte Seite des Pivots sind größer als der Pivot. Wir können Quicksort auf die linke und rechte Partition anwenden, um die gesamte Liste zu sortieren.

Was ist Mergesort?

Zusammenführungssortierung ist ein externer Algorithmus, der die Technik "Teilen und Erobern" verwendet. Es teilt das Array in zwei Abschnitte auf. Es sortiert jedes Array und kombiniert sie, um das sortierte Array zu bilden. Die Zusammenführungssortierung erfordert zusätzlichen Speicher zum Sortieren des Hilfsarrays.

Betrachten Sie das folgende Beispiel.

Abbildung 2: Sortierreihenfolge

Wir können das Array in zwei Abschnitte unterteilen. Jetzt gibt es zwei Arrays wie folgt.

38 27 43 3 9 82 10

Betrachten Sie 38 27 43 3. Wir können es wieder in zwei Arrays unterteilen. Sie sind 38 27 und 43 3. 38 27 teilt sich in 38 und 27 auf, während 43 3 sich in 43 und 3 aufteilt. Die Sortierung 38 und 27 ergibt 27 38. Die Sortierung 43 3 ergibt 3 43. Nun ist es möglich, 27 38 und 3 43 zu kombinieren Nachdem wir sie sortiert haben, erhalten wir ein Array als 3 27 38 43. 

Betrachten Sie ebenfalls 9 82 10. Wir können es wieder in zwei Arrays unterteilen. Sie sind 9 82 und 10. 9 82 teilt sich in 9 und 82 auf. Darüber hinaus gibt es die Nummer 10 in dem anderen Feld. 9 und 82 sortieren als 9 82. Somit fasst dieses Array und dieses Array mit dem Wert 10 9, 10 und 82 zusammen und liefert sie.

Schließlich kombinieren 3 27 38 43 und 9 10 82 das sortierte Array.

Unterschied zwischen Quicksort und Merge Sort

Definition

Quicksort ist ein effizienter Sortieralgorithmus, der als systematische Methode zum Ordnen der Elemente eines Arrays dient. Im Gegensatz dazu ist die Zusammenführungssortierung ein effizienter Vergleichssortieralgorithmus für allgemeine Zwecke. Dies ist also der grundlegende Unterschied zwischen Quicksortierung und Zusammenführungssortierung.

Funktionalität

Vor allem die Funktionalität ist der Hauptunterschied zwischen Quicksortierung und Zusammenführungssortierung. Quicksort sortiert die Elemente, indem jedes Element mit dem Drehpunkt verglichen wird, während bei der Zusammenführungssortierung das Array immer wieder in zwei Unterfelder (n / 2) unterteilt wird, bis ein Element übrig bleibt.

Anwendung

Während Quicksort für kleine Arrays geeignet ist, funktioniert die Zusammenführungssortierung für jeden Array-Typ.

Geschwindigkeit

Ein weiterer Unterschied zwischen Quicksort- und Zusammenführungssortierung besteht darin, dass der Quicksort für kleine Datensätze schneller arbeitet, während die Zusammenführungssortierung für alle Datensätze mit gleichbleibender Geschwindigkeit arbeitet.

Platzbedarf

Darüber hinaus ist der Platzbedarf auch ein wichtiger Unterschied zwischen der Sortierung von Quicksortierung und Zusammenführung. Quicksort benötigt im Vergleich zur Zusammenführungssortierung nur minimalen Speicherplatz.  

Effizienz

Außerdem ist Quicksort für große Arrays nicht effizient, die Zusammenführungssortierung ist jedoch effizienter als Quicksort. Daher ist dies ein weiterer Unterschied zwischen der Sortierung von Quicksortierung und Zusammenführung.

Fazit

Zusammenfassend ist der Hauptunterschied zwischen quicksort und merge sort der, dass der quicksort die Elemente sortiert, indem er jedes Element mit einem Element namens Pivot vergleicht, während die merge sort das Array immer wieder in zwei Unterfelder aufteilt, bis ein Element übrig bleibt.

Referenz:

1. Quicksort-Algorithmus | Teil 2, Bildung 4u, 15. März 2018, hier verfügbar.
2. Zusammenführungssortierbeispiel, Education 4u, 15. März 2018, verfügbar hier.

Bildhöflichkeit:

1. „Quicksort-Diagramm“ von Znupi - Eigene Arbeit (Public Domain) über Commons Wikimedia
2. „Merge-Sort-Algorithmus-Diagramm“ Von Vineet Kumar in der Wikipedia auf Englisch - Von en.wikipedia an Commons übertragen von Eric Bauman mit CommonsHelper (Public Domain) über Commons Wikimedia