quick sort c with examples
Quicksort in C ++ mit Illustration.
Quicksort ist ein weit verbreiteter Sortieralgorithmus, der ein bestimmtes Element namens 'Pivot' auswählt und das zu sortierende Array oder die Liste basierend auf diesem Pivot s0 in zwei Teile unterteilt, sodass sich die Elemente, die kleiner als der Pivot sind, links von der Liste und den Elementen befinden größer als der Drehpunkt sind rechts von der Liste.
Somit ist die Liste in zwei Unterlisten unterteilt. Die Unterlisten sind möglicherweise nicht für dieselbe Größe erforderlich. Dann ruft sich Quicksort rekursiv auf, um diese beiden Unterlisten zu sortieren.
=> Lesen Sie hier den perfekten C ++ - Schulungsleitfaden.
Was du lernen wirst:
- Einführung
- Allgemeiner Algorithmus
- Pseudocode für Quicksort
- Illustration
- C ++ Beispiel
- Java-Beispiel
- Komplexitätsanalyse des Quicksort-Algorithmus
- 3-Wege-Quicksort
- Randomisierte Quicksort
- Quicksort vs. Merge Sort
- Fazit
- Literatur-Empfehlungen
Einführung
Quicksort arbeitet auch bei größeren Arrays oder Listen effizient und schneller.
In diesem Tutorial werden wir mehr über die Arbeitsweise von Quicksort sowie einige Programmierbeispiele des Quicksort-Algorithmus erfahren.
Als Pivot-Wert können wir entweder den ersten, den letzten oder den mittleren Wert oder einen beliebigen Zufallswert auswählen. Die allgemeine Idee ist, dass der Pivot-Wert letztendlich an der richtigen Position im Array platziert wird, indem die anderen Elemente im Array nach links oder rechts verschoben werden.
Allgemeiner Algorithmus
Der allgemeine Algorithmus für Quicksort ist unten angegeben.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Schauen wir uns nun den Pseudocode für die Quicksort-Technik an.
Pseudocode für Quicksort
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Die Funktionsweise des Partitionierungsalgorithmus wird im Folgenden anhand eines Beispiels beschrieben.
In dieser Abbildung nehmen wir das letzte Element als Drehpunkt. Wir können sehen, dass das Array nacheinander um das Pivot-Element herum aufgeteilt wird, bis wir ein einzelnes Element im Array haben.
Jetzt präsentieren wir eine Illustration des Quicksort unten, um das Konzept besser zu verstehen.
Illustration
Lassen Sie uns eine Illustration des Quicksort-Algorithmus sehen. Betrachten Sie das folgende Array mit dem letzten Element als Drehpunkt. Außerdem ist das erste Element als niedrig und das letzte Element als hoch gekennzeichnet.
beste kostenlose Anti-Spyware für PC
Aus der Abbildung können wir erkennen, dass wir die Zeiger an beiden Enden des Arrays hoch und niedrig bewegen. Immer wenn niedrige Punkte auf das Element größer als der Drehpunkt und hohe Punkte auf das Element kleiner als der Drehpunkt sind, tauschen wir die Positionen dieser Elemente aus und bewegen die niedrigen und hohen Zeiger in ihre jeweiligen Richtungen.
Dies geschieht so lange, bis sich die niedrigen und hohen Zeiger kreuzen. Sobald sie sich kreuzen, wird das Pivot-Element an der richtigen Position platziert und das Array in zwei Teile geteilt. Dann werden diese beiden Unterarrays unabhängig voneinander mithilfe von Quicksort rekursiv sortiert.
C ++ Beispiel
Im Folgenden wird die Implementierung des Quicksort-Algorithmus in C ++ angegeben.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Ausgabe:
Eingabearray
12 23 3 43 51 35 19 45
Array mit Quicksort sortiert
3 12 19 23 35 43 45 51
Hier haben wir einige Routinen, die zum Partitionieren des Arrays und zum rekursiven Aufrufen von Quicksort verwendet werden, um die Partition zu sortieren, grundlegende Quicksort-Funktionen und Dienstprogrammfunktionen, um den Array-Inhalt anzuzeigen und die beiden Elemente entsprechend auszutauschen.
Zuerst rufen wir die Quicksort-Funktion mit dem Eingabearray auf. Innerhalb der Quicksort-Funktion rufen wir die Partitionsfunktion auf. In der Partitionsfunktion verwenden wir das letzte Element als Pivot-Element für das Array. Sobald der Pivot festgelegt ist, wird das Array in zwei Teile aufgeteilt, und dann wird die Quicksort-Funktion aufgerufen, um beide Sub-Arrays unabhängig voneinander zu sortieren.
Wenn die Quicksort-Funktion zurückkehrt, wird das Array so sortiert, dass sich das Pivot-Element an der richtigen Position befindet und sich die Elemente, die kleiner als der Pivot sind, links vom Pivot und die Elemente, die größer als der Pivot sind, rechts vom Pivot befinden.
Als nächstes werden wir den Quicksort-Algorithmus in Java implementieren.
Java-Beispiel
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Ausgabe:
Blasensortierung c ++ Code
Eingabearray
12 23 3 43 51 35 19 45
Array nach dem Sortieren mit Quicksort
3 12 19 23 35 43 45 51
Auch in der Java-Implementierung haben wir dieselbe Logik verwendet, die wir in der C ++ - Implementierung verwendet haben. Wir haben das letzte Element im Array verwendet, da der Pivot- und QuickSort-Vorgang für das Array ausgeführt wird, um das Pivot-Element an der richtigen Position zu platzieren.
Komplexitätsanalyse des Quicksort-Algorithmus
Die Zeit, die Quicksort zum Sortieren eines Arrays benötigt, hängt von der Eingabearray- und Partitionsstrategie oder -methode ab.
Wenn k die Anzahl der Elemente ist, die kleiner als der Drehpunkt ist, und n die Gesamtzahl der Elemente ist, kann die allgemeine Zeit, die Quicksort benötigt, wie folgt ausgedrückt werden:
T (n) = T (k) + T (n-k-1) + O (n)
Hier sind T (k) und T (n-k-1) die Zeit, die von rekursiven Aufrufen benötigt wird, und O (n) ist die Zeit, die von Partitionierungsaufrufen benötigt wird.
Lassen Sie uns diese Zeitkomplexität für QuickSort im Detail analysieren.
# 1) Schlimmster Fall : Der schlimmste Fall in der Quicksort-Technik tritt meistens auf, wenn wir das niedrigste oder höchste Element im Array als Drehpunkt auswählen. (In der obigen Abbildung haben wir das höchste Element als Drehpunkt ausgewählt.) In einer solchen Situation tritt der schlimmste Fall auf, wenn das zu sortierende Array bereits in aufsteigender oder absteigender Reihenfolge sortiert ist.
Daher ändert sich der obige Ausdruck für die Gesamtzeit wie folgt:
T (n) = T (0) + T (n-1) + O (n) das löst sich auf Aufzwei)
# 2) Bester Fall: Der beste Fall für Quicksort tritt immer dann auf, wenn das ausgewählte Pivot-Element in der Mitte des Arrays liegt.
Somit ist die Wiederholung für den besten Fall:
Hash-Tabelle C ++ Beispiel
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Durchschnittlicher Fall: Um den Durchschnittsfall für Quicksort zu analysieren, sollten wir alle Array-Permutationen berücksichtigen und dann die Zeit berechnen, die jede dieser Permutationen benötigt. Kurz gesagt, die durchschnittliche Zeit für die Quicksortierung wird ebenfalls zu O (nlogn).
Nachstehend sind die verschiedenen Komplexitäten für die Quicksort-Technik aufgeführt:
Zeitkomplexität im schlimmsten Fall O (n 2) Stabilität Nicht stabil, da zwei Elemente mit denselben Werten nicht in derselben Reihenfolge platziert werden. Stabil - Zwei Elemente mit denselben Werten werden in der sortierten Ausgabe in derselben Reihenfolge angezeigt. Best-Case-Zeitkomplexität O (n * log n) Durchschnittliche Zeitkomplexität O (n * log n) Raumkomplexität O (n * log n)
Wir können Quicksort auf viele verschiedene Arten implementieren, indem wir einfach die Auswahl des Pivot-Elements (Mitte, Erste oder Letzte) ändern. Der schlimmste Fall tritt jedoch bei Quicksort selten auf.
3-Wege-Quicksort
Bei der ursprünglichen Quicksort-Technik wählen wir normalerweise ein Pivot-Element aus und teilen das Array dann in Sub-Arrays um diesen Pivot auf, sodass ein Sub-Array aus Elementen besteht, die kleiner als der Pivot sind, und ein anderes aus Elementen, die größer als der Pivot sind.
Was aber, wenn wir ein Pivot-Element auswählen und mehr als ein Element im Array vorhanden ist, das dem Pivot entspricht?
Zum Beispiel, Betrachten Sie das folgende Array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Wenn wir eine einfache Quicksortierung für dieses Array durchführen und 4 als Pivot-Element auswählen, wird nur ein Vorkommen von Element 4 behoben und der Rest wird zusammen mit den anderen Elementen partitioniert.
Wenn wir stattdessen 3-Wege-Quicksort verwenden, teilen wir das Array (l… r) wie folgt in drei Sub-Arrays auf:
- Array (l… i) - Hier ist i der Pivot und dieses Array enthält Elemente, die kleiner als der Pivot sind.
- Array (i + 1… j-1) - Enthält die Elemente, die dem Pivot entsprechen.
- Array (j… r) - Enthält Elemente, die größer als der Drehpunkt sind.
Somit kann 3-Wege-Quicksort verwendet werden, wenn mehr als ein redundantes Element im Array vorhanden ist.
Randomisierte Quicksort
Die Quicksort-Technik wird als randomisierte Quicksort-Technik bezeichnet, wenn Zufallszahlen zur Auswahl des Pivot-Elements verwendet werden. In der randomisierten Quicksortierung wird sie als 'zentraler Drehpunkt' bezeichnet und teilt das Array so auf, dass jede Seite mindestens ¼ Elemente enthält.
Der Pseudocode für randomisierte Quicksortierung ist unten angegeben:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureIm obigen Code für 'randomQuickSort' wählen wir in Schritt 2 den zentralen Drehpunkt aus. In Schritt 2 beträgt die Wahrscheinlichkeit, dass das ausgewählte Element der zentrale Drehpunkt ist, ½. Daher wird erwartet, dass die Schleife in Schritt 2 zweimal ausgeführt wird. Somit ist die Zeitkomplexität für Schritt 2 in randomisierter Quicksortierung O (n).
Die Verwendung einer Schleife zur Auswahl des zentralen Drehpunkts ist nicht der ideale Weg, um eine zufällige Quicksortierung zu implementieren. Stattdessen können wir ein Element zufällig auswählen und es als zentralen Drehpunkt bezeichnen oder die Array-Elemente neu mischen. Die erwartete Zeitkomplexität im ungünstigsten Fall für einen randomisierten Quicksort-Algorithmus ist O (nlogn).
Quicksort vs. Merge Sort
In diesem Abschnitt werden die Hauptunterschiede zwischen Schnellsortierung und Zusammenführungssortierung erläutert.
Vergleichsparameter Schnelle Sorte Zusammenführen, sortieren Partitionierung Das Array ist um ein Pivot-Element verteilt und besteht nicht unbedingt immer aus zwei Hälften. Es kann in jedem Verhältnis partitioniert werden. Das Array ist in zwei Hälften unterteilt (n / 2). Komplexität im schlimmsten Fall O (n 2) - im schlimmsten Fall sind viele Vergleiche erforderlich. O (nlogn) - wie im Durchschnitt Verwendung von Datensätzen Kann mit größeren Datenmengen nicht gut funktionieren. Funktioniert gut mit allen Datensätzen, unabhängig von der Größe. Zusätzlicher Platz An Ort und Stelle - benötigt keinen zusätzlichen Platz. Nicht vorhanden - benötigt zusätzlichen Speicherplatz zum Speichern des Zusatzarrays. Sortiermethode Intern - Daten werden im Hauptspeicher sortiert. Extern - Verwendet externen Speicher zum Speichern von Datenarrays. Effizienz Schneller und effizienter für kleine Listen. Schnell und effizient für größere Listen. Arrays / verknüpfte Listen Bevorzugter für Arrays. Funktioniert gut für verknüpfte Listen.
Fazit
Wie der Name schon sagt, ist Quicksort der Algorithmus, der die Liste schneller sortiert als alle anderen Sortieralgorithmen. Genau wie beim Zusammenführen von Sortierungen wird auch beim schnellen Sortieren eine Strategie zum Teilen und Erobern angewendet.
Wie wir bereits gesehen haben, teilen wir die Liste mithilfe der schnellen Sortierung mithilfe des Pivot-Elements in Unterarrays auf. Dann werden diese Unterarrays unabhängig voneinander sortiert. Am Ende des Algorithmus wird das gesamte Array vollständig sortiert.
Quicksort ist schneller und arbeitet effizient zum Sortieren von Datenstrukturen. Quicksort ist ein beliebter Sortieralgorithmus und wird manchmal sogar dem Sortieralgorithmus vorgezogen.
In unserem nächsten Tutorial werden wir detaillierter auf die Shell-Sortierung eingehen.
=> Sehen Sie sich hier die einfache C ++ - Schulungsserie an.
Literatur-Empfehlungen
- MongoDB Sort () -Methode mit Beispielen
- Unix-Sortierbefehl mit Syntax, Optionen und Beispielen
- Sortierung in C ++ mit Beispielen zusammenführen
- Heap-Sortierung in C ++ mit Beispielen
- Shell-Sortierung in C ++ mit Beispielen
- Auswahl In C ++ mit Beispielen sortieren
- Blasensortierung in C ++ mit Beispielen
- Einfügungssortierung in C ++ mit Beispielen
