QuickSort ist ein Sortieralgorithmus, der eine Teile-und-herrsche-Strategie verwendet, um ein Array aufzuteilen und zu sortieren. Die Zeitkomplexität beträgt O nlogn.
Sortieren ist der Prozess, Elemente auf strukturierte Weise zu organisieren. QuickSort ist einer der beliebtesten Sortieralgorithmen , der in einer typischen Situation Vergleiche verwendet , um ein Array von n Elementen zu sortieren. QuickSort basiert auf der Teile-und-herrsche-Strategie. nlogn
Wir werden uns in diesem Tutorial den Quicksort-Algorithmus ansehen und sehen, wie er funktioniert.
Was ist QuickSort?
QuickSort ist ein schneller Sortieralgorithmus, der ein großes Datenarray in kleinere Unterarrays aufteilt . Das bedeutet, dass jede Iteration die Eingabe in zwei Komponenten aufteilt, diese sortiert und dann neu kombiniert. Die Technik ist für große Datensätze hocheffizient , da ihre durchschnittliche und beste Komplexität beträgt O(n*logn).
QuickSort wurde 1961 von Tony Hoare entwickelt und ist nach wie vor einer der effektivsten Sortieralgorithmen für allgemeine Zwecke, die heute verfügbar sind. Es funktioniert, indem die Unterlisten auf beiden Seiten eines bestimmten Pivots rekursiv sortiert werden und Elemente innerhalb der Liste dynamisch um diesen Pivot herum verschoben werden.
Insgesamt kann die Quicksort-Methode in drei Schritten zusammengefasst werden:
- Auswählen: Wählen Sie ein Element aus.
- Teilen: Teilen Sie den Aufgabensatz auf, verschieben Sie kleinere Teile nach links vom Pivot und größere Elemente nach rechts.
- Wiederholen und kombinieren: Wiederholen Sie die Schritte und kombinieren Sie die zuvor sortierten Arrays.
Wie funktioniert QuickSort?
Schauen wir uns ein Beispiel an, um den Quicksort-Algorithmus besser zu verstehen. In diesem Beispiel enthält das folgende Array unsortierte Werte, die wir mit Quicksort sortieren werden.
1. Wählen Sie einen Pivot
Der Vorgang beginnt mit der Auswahl eines Pivot-Elements aus der Liste. Dies kann jedes beliebige Element sein. Ein Pivot kann sein:
- Jedes beliebige Element nach dem Zufallsprinzip.
- Das erste oder letzte Element.
- Mittleres Element.
Für dieses Beispiel verwenden wir das letzte Element 4als Pivot.
2. Ordnen Sie das Array neu an
Das Ziel besteht nun darin, die Liste so umzuordnen, dass alle Elemente, die kleiner als der Pivot sind, links davon und alle Elemente, die größer als der Pivot sind, rechts davon stehen. Denken Sie daran:
- Das Pivot-Element wird mit allen Elementen ab dem ersten Index verglichen. Wenn das Element größer als das Pivot-Element ist, wird ein zweiter Zeiger angehängt.
- Wenn beim Vergleich mit anderen Elementen ein kleineres Element als das Pivot-Element gefunden wird, wird das kleinere Element mit dem zuvor identifizierten größeren Element vertauscht.
Vereinfachen wir das obige Beispiel.
- Jedes Element, beginnend mit 7, wird mit dem Pivot( 4) verglichen. Ein zweiter Zeiger wird bei platziert, 7da 7größer als ist 4.
- Das nächste Element, Element, 2wird nun mit dem Pivot verglichen. Da 2kleiner als ist 4, wird es durch die größere Zahl ersetzt 7, die zuvor gefunden wurde.
- Die Zahlen 7und 2werden vertauscht. Jetzt wird Pivot mit dem nächsten Element verglichen, 1das kleiner als ist 4.
- Also wird noch einmal 7mit getauscht 1.
- Der Vorgang wird so lange fortgesetzt, bis das vorletzte Element erreicht ist. Am Ende wird dann das Pivot-Element durch den zweiten Zeiger ersetzt. Dabei 4wird number (pivot) durch number ersetzt 6.
Da die Elemente 2, 1, und 3kleiner als sind 4, stehen sie auf der linken Seite des Pivots. Die Elemente können in beliebiger Reihenfolge stehen: ‘1’,’2’,’3’, or ‘3’,’1’,’2’, oder‘2’,’3’,’1’ . Die einzige Voraussetzung ist, dass alle Elemente kleiner als der Pivot sein müssen. Ebenso müssen auf der rechten Seite, unabhängig von ihrer Reihenfolge, alle Komponenten größer als der Pivot sein.
Mit anderen Worten sucht der Algorithmus nach jedem Wert, der kleiner als der Pivot ist. Werte, die kleiner als der Pivot sind, werden links platziert, während Werte, die größer als der Pivot sind, rechts platziert werden. Sobald die Werte neu angeordnet sind, wird der Pivot an seine sortierte Position gesetzt.
3. Teilen Sie die Subarrays auf
Nachdem wir das Array partitioniert haben, können wir dieses Problem in zwei Unterprobleme aufteilen. Sortieren Sie zuerst das Segment des Arrays links vom Pivot und dann das Segment des Arrays rechts vom Pivot.
- Auf die gleiche Weise, wie wir in Schritt zwei die Elemente neu angeordnet haben, wählen wir für jedes der linken und rechten Unterteile einzeln ein Pivot-Element aus.
- Nun ordnen wir die Unterliste so um, dass alle Elemente kleiner sind als der Pivotpunkt, der sich weiter links befindet. Beispielsweise 3ist das Element das größte der drei Elemente, was die Bedingung erfüllt. Daher 3befindet sich das Element an seiner sortierten Position.
- Auf ähnliche Weise werden wir erneut an der Unterliste arbeiten und die Elemente 2und sortieren 1. Wir werden den Vorgang beenden, wenn wir am Ende ein einzelnes Element erhalten.
- Wiederholen Sie den gleichen Vorgang für die rechte Unterliste. Die Unterarrays werden so lange unterteilt, bis jedes Unterarray nur noch aus einem Element besteht .
- Jetzt ist das Array sortiert.
Vorteile und Nachteile von QuickSort
Lassen Sie uns einige wichtige Vorteile der Verwendung von Quicksort durchgehen:
- Es wirkt schnell und effektiv.
- Es weist im Vergleich zu anderen Sortieralgorithmen die beste Zeitkomplexität auf.
- QuickSort hat eine Speicherkomplexität von O(logn)und ist daher eine ausgezeichnete Wahl für Situationen, in denen der Speicherplatz begrenzt ist.
Obwohl Quicksort der schnellste Algorithmus ist, weist es einige Nachteile auf. Sehen wir uns einige der Nachteile von Quicksort an.
- Diese Sortiertechnik gilt als instabil, da die ursprüngliche Reihenfolge der Schlüssel-Wert-Paare nicht beibehalten wird .
- Es ist nicht so effektiv, wenn das Pivot-Element das größte oder kleinste ist oder wenn alle Komponenten die gleiche Größe haben. Die Leistung des Quicksorts wird durch diese Worst-Case-Szenarien erheblich beeinträchtigt.
- Da es sich um einen rekursiven Prozess handelt, ist die Implementierung schwierig, insbesondere wenn keine Rekursion verfügbar ist.
Codebeispiel für den QuickSort-Algorithmus
Algorithmus der QuickSort-Funktion
QuickSort-Partitionsfunktionsalgorithmus
Mithilfe der Partitionsmethode werden die Subarrays in einer bestimmten Reihenfolge neu angeordnet. Es gibt verschiedene Möglichkeiten zur Partitionierung. Hier sehen wir eine der am häufigsten verwendeten Methoden.
So implementieren Sie QuickSort in JavaScript
Schauen wir uns Quicksort-Programme an, die in den Programmiersprachen JavaScript und Python geschrieben sind. Wir beginnen mit der Erstellung einer Funktion, mit der Sie zwei Komponenten austauschen können.
Fügen wir nun eine Funktion hinzu, die das letzte Element (den letzten Wert) als Pivot verwendet, alle kleineren Elemente nach links vom Pivot und alle größeren Elemente nach rechts vom Pivot verschiebt und den Pivot an der entsprechenden Stelle im sortierten Array platziert.
Als Nächstes fügen wir die Hauptfunktion hinzu, die die Elemente partitioniert und sortiert.
Zum Abschluss fügen wir eine Funktion zum Drucken des Arrays hinzu.
Hier ist der vollständige Code der Quicksort-Implementierung für JavaScript:
So implementieren Sie QuickSort in Python
Schauen wir uns nun Quicksort-Programme an, die in Python geschrieben sind . Wir beginnen mit der Erstellung einer Funktion, die für das Sortieren der ersten und letzten Elemente eines Arrays zuständig ist.
Als Nächstes fügen wir die Hauptfunktion hinzu, die implementiert quick_sort.
Zum Abschluss fügen wir eine Funktion zum Drucken des Arrays hinzu.
Hier ist der vollständige Code der Quicksort- Implementierung in Python .
Zeitliche Komplexität für QuickSort
Schauen wir uns die räumliche und zeitliche Komplexität von Quicksort im besten, durchschnittlichen und schlimmsten Fall an. Generell kann die von Quicksort benötigte Zeit wie folgt ausgedrückt werden:
Hier beziehen sich T(k)und T(n-k-1) auf zwei rekursive Aufrufe, während sich der letzte Term O(n)auf den Partitionierungsprozess bezieht. Die Anzahl der Elemente, die kleiner als Pivot sind, wird durch bezeichnet k.
1. QuickSort Best-Case-Zeitkomplexität
Wenn der Partitionierungsalgorithmus immer das mittlere oder ein nahe dem mittleren Element liegendes Element als Pivot wählt, ist das beste Szenario gegeben. Die beste Zeitkomplexität von Quicksort beträgt O (n*logn). Das Folgende ist die beste Wiederholung.
2. QuickSort-Zeitkomplexität im durchschnittlichen Fall
Dies tritt auf, wenn die Array-Elemente in einer ungeordneten Sequenz vorliegen, die nicht richtig zunimmt oder abnimmt. Die durchschnittliche Zeitkomplexität von QuickSort beträgt O(n*logn). Das Folgende ist die durchschnittliche Wiederholung.
3. QuickSort – Worst-Case-Zeitkomplexität
Der schlimmste Fall liegt vor, wenn der Partitionierungsalgorithmus jedes Mal das größte oder kleinste Element als Pivot-Element auswählt. Die Zeitkomplexität von Quicksort im schlimmsten Fall beträgt O (n2). Das Folgende ist die Wiederholung im schlimmsten Fall.
QuickSort- Speicherplatzkomplexität
Die Speicherkomplexität für Quicksort beträgt O(log n).
Quicksort-Anwendungen
Der Sortieralgorithmus wird zum Suchen von Informationen verwendet und da Quicksort der schnellste ist, wird er häufig als effizientere Suchmethode verwendet.
- Es wird überall dort angewendet, wo eine stabile Sortierung nicht erforderlich ist.
- Da es endrekursiv ist, kann jede Anrufoptimierung durchgeführt werden.
- Es ist nützlich in der ereignisgesteuerten Simulation und der operativen Forschung.
Ist QuickSort besser als andere Sortieralgorithmen?
QuickSort hat zwar einige Nachteile, ist aber der schnellste und effizienteste Sortieralgorithmus auf dem Markt. QuickSort weist eine O (logn)Speicherkomplexität auf und ist daher eine ausgezeichnete Wahl für Situationen, in denen der Speicherplatz begrenzt ist.
Obwohl die Laufzeit im schlimmsten Fall immer gleich ist, ist Quicksorts oft schneller als Heapsort (nlogn) . QuickSort benötigt weniger Speicherplatz als Heapsort, da ein Heap fast ein vollständiger Binärbaum mit Zeigern ist. Wenn es also um das Sortieren von Arrays geht, ist Quicksorts vorzuziehen.
Warum QuickSorts nützlich ist
Quicksorts hat zwar einige Nachteile, ist aber der schnellste Sortieralgorithmus auf dem Markt. QuickSort ist ein effizienter Algorithmus, der in der Praxis gute Ergebnisse liefert.
In diesem Artikel haben wir erfahren, was Quicksorts ist, welche Vor- und Nachteile es hat und wie es implementiert wird.