Quick Sort ähnelt dem Merge Sort in dem Sinne, dass dieser Algorithmus dem Programmierer hilft, zu teilen und zu erobern. Er wählt Elemente als Dreh- und Angelpunkt aus und erstellt dann Partitionen im Array. Quick Sort hat zahlreiche Versionen, und jede von ihnen wählt den Pivot anders aus.
Der Befehl partition() ist wohl der wichtigste Teil von quick sort. Partitionsziele erhalten ein Array mit einem Arrayelement x als Pivot. Sie müssen das x an der richtigen Stelle platzieren, d. h. im sortierten Array, und anschließend Elemente, die kleiner als x sind, davor platzieren. Schließlich müssen Sie Elemente, die größer als x sind, dahinter platzieren. Stellen Sie sicher, dass Sie all dies in linearer Zeit erledigen.
Man sollte auch bedenken, dass quick sort Partitionen in Arrays erzeugt, nach denen es sich selbst zweimal wiederholt, um die daraus resultierenden Subarrays zu sortieren. Ein Algorithmus wie dieser ist bei großen Datensätzen unglaublich praktisch. Der Grund dafür ist, dass die Komplexität im schlimmsten Fall O(n2) ist. Die beiden Anfangsterme sind für rekursive Aufrufe gedacht, während der letzte Term bei der Partitionierung nützlich ist. Die Elemente, die kleiner als der Pivot sind, werden durch k dargestellt.
Die Zeit, die Quick Sort in der Regel benötigt, hängt von der Partitionsstrategie und dem Eingabefeld ab.
Die drei Fälle von Quick Sort
Wie bei verschiedenen anderen Sortieralgorithmen gibt es auch bei Quick Sort Fallbeispiele. Diese werden im Folgenden besprochen:
Schlechtester Fall
Dieser Fall tritt immer dann ein, wenn der Partitionsprozess das kleinste oder größte Element als Pivot wählt. In Anbetracht der zuvor besprochenen Partitionsstrategie, bei der jedes Mal das letzte Element als Pivot gewählt wird, tritt das Worst-Case-Szenario auf, sobald das Array in absteigender oder aufsteigender Reihenfolge sortiert wird. Die Rekursion für den schlechtesten Fall lautet wie folgt:
T(n) = T(0) + T(n-1) + (n), was gleichbedeutend ist mit T(n) = T(n-1) + (n)
Bester Fall
Der beste Fall tritt immer dann ein, wenn der Partitionsprozess das mittlere Element als Drehpunkt wählt. Die Rekursion für den besten Fall ist wie folgt:
T(n) = 2T(n/2) + (n)
Durchschnittlicher Fall
Man muss jede Array-Permutation betrachten und die Zeit berechnen, die jede Permutation für die Durchführung einer Fallanalyse benötigt. Natürlich kann dieser Vorgang selbst für erfahrene Programmierer recht kompliziert sein. Wenn man jedoch den Fall betrachtet, dass die Partition O(n/9) zusammen mit O(9n/10) Elementen platziert, kann man eine Schätzung des durchschnittlichen Falls erhalten. Die Rekursion für diesen Fall ist wie folgt.
T(n) = T(n/9) + T(9n/10) + (n)
Häufig gestellte Fragen zu Quick Sort
Es gibt viele Fragen, die zu Quick Sort gestellt werden, aber die unten aufgeführten sind wohl die häufigsten:
Ist quick sort ein stabiler Algorithmus?
Nun, die Standardimplementierung von quick sort ist nicht stabil. Es ist jedoch möglich, die Stabilität von Sortieralgorithmen zu erhöhen, indem der Index als Vergleichsparameter herangezogen wird.
Was ist eine dreifache Quicksortierung?
Bei einem regulären Quick-Sort-Algorithmus wählen wir ein Element, das als Pivot fungiert, und erstellen eine Partition im Array. Danach werden die Unterfelder auf der rechten und linken Seite des Pivots rekurriert.
Ist Quick Sort ein In-Place-Algorithmus?
Nach der weit gefassten Definition des In-Place-Algorithmus gehört Quick Sort tatsächlich zu dieser Art von Sortieralgorithmus. Dies liegt daran, dass er zusätzlichen Platz zum Speichern rekursiver Funktionsaufrufe verwendet. Die Eingabe wird jedoch in keiner Weise manipuliert.
Schneller als die meisten Sortieralgorithmen
Es lässt sich zwar nicht leugnen, dass die Zeitkomplexität von quick sort im ungünstigsten Fall O(n2) beträgt und damit höher ist als bei heap sort, merge sort und zahlreichen anderen Sortieralgorithmen, aber quick sort ist dennoch unglaublich schnell. Einer der Gründe dafür ist, dass man seine innere Schleife in verschiedenen Arten von Daten und Architekturen der realen Welt effizient implementieren kann.
Darüber hinaus kann quick sort auf verschiedene Arten implementiert werden, indem man einfach die Wahl des Pivots ändert. Dadurch wird das Auftreten des schlimmsten Falls für jeden Datentyp minimiert. Dennoch bevorzugen Programmierer im Allgemeinen die Merge-Sortierung, wenn die Datenmenge zu groß ist, insbesondere wenn sie sich in einem externen Speicher befindet.
Was ist mit der Verwendung von Quick Sort in verknüpften Listen?
Bei verknüpften Listen liegen die Dinge aufgrund der Unterschiede in der Speicherzuweisung des Arrays ganz anders. Verknüpfte Listenknoten sind ganz anders als Arrays und liegen im Speicher oft nicht nebeneinander. Außerdem können Sie bei verknüpften Listen Elemente in der Mitte eingeben, was bei Arrays nicht möglich ist. In solchen Szenarien bevorzugen Programmierer die Merge-Sortierung, da sie sich im Vergleich zur Quick-Sortierung als praktikablere Option erweist.
Warum Programmierer Quick Sort zum Sortieren von Arrays bevorzugen
Im Kern ist Quick Sort eine einfache In-Place-Sortierung, d. h. sie benötigt keinen zusätzlichen Speicherplatz. Auf der anderen Seite benötigt merge sort O(N) zusätzlichen Speicherplatz. Für diejenigen, die sich wundern: N steht für die Größe des Arrays, die unglaublich umfangreich sein kann. Das Aufheben der Zuweisung und die Zuweisung des zusätzlichen Speicherplatzes, der für Merge-Sort benötigt wird, erhöht die Laufzeit des Algorithmus.
Wenn wir die durchschnittliche Komplexität vergleichen, ist es leicht zu erkennen, dass die durchschnittliche Komplexität beider Sortierarten O(NlogN) ist. Ihre Konstanten sind jedoch unterschiedlich. Bei Arrays ist die Merge-Sortierung nicht erfolgreich, da sie zusätzlichen O(N)-Speicherplatz benötigt. Die meisten praktischen Implementierungen der schnellen Sortierung verwenden die randomisierte Version. Die durchschnittliche Zeitkomplexität dieser Version ist O(nLogn). Es sollte auch bedacht werden, dass bei der randomisierten Version die Möglichkeit eines schlechteren Falls besteht. Dieser tritt jedoch bei bestimmten Mustern, wie z. B. sortierten Arrays, nicht auf.
Der Quick-Sort-Algorithmus ist aufgrund seiner exzellenten Lokalität recht cache-freundlich, insbesondere wenn man ihn für Arrays verwendet. Darüber hinaus ist quick sort auch tail-rekursiv, was bedeutet, dass Sie tail-call-Optimierungen durchführen müssen.