quicksort java algorithm
In diesem Tutorial werden der Quicksort-Algorithmus in Java, seine Abbildungen und die QuickSort-Implementierung in Java anhand von Codebeispielen erläutert:
Die Quicksort-Sortiertechnik ist in Softwareanwendungen weit verbreitet. Quicksort verwendet eine Divide-and-Conquer-Strategie wie Merge Sort.
Beim Quicksort-Algorithmus wird zuerst ein spezielles Element namens 'Pivot' ausgewählt und das betreffende Array oder die betreffende Liste in zwei Teilmengen aufgeteilt. Die partitionierten Teilmengen können gleich groß sein oder nicht.
=> Lesen Sie die Easy Java Training Series durch.
Die Trennwände sind so angeordnet, dass alle Elemente, die kleiner als das Drehelement sind, links vom Drehpunkt liegen und die Elemente, die größer als der Drehpunkt sind, rechts vom Drehpunkt liegen. Die Quicksort-Routine sortiert die beiden Unterlisten rekursiv. Quicksort arbeitet effizient und auch schneller, selbst bei größeren Arrays oder Listen.
Was du lernen wirst:
- Quicksort Partition Java
- Quicksort-Algorithmus Java
- Pseudocode zum schnellen Sortieren
- Illustration
- Quicksort-Implementierung in Java
- Häufig gestellte Fragen
- Fazit
- Literatur-Empfehlungen
Quicksort Partition Java
Partitionierung ist der Schlüsselprozess der Quicksort-Technik. Was ist Partitionierung?
Bei einem Array A wählen wir einen Wert x, der als Pivot bezeichnet wird, so dass alle Elemente kleiner als x vor x und alle Elemente größer als x nach x stehen.
Ein Pivot-Wert kann einer der folgenden sein:
- Das erste Element im Array
- Das letzte Element im Array
- Das mittlere Element im Array
- Beliebiges zufälliges Element im Array
Dieser Pivot-Wert wird dann durch Partitionieren des Arrays an der richtigen Position im Array platziert. Die Ausgabe des Partitionierungsprozesses ist also der Pivot-Wert an der richtigen Position und die Elemente, die links weniger als Pivot sind, und die Elemente, die rechts größer als ein Pivot sind.
Betrachten Sie das folgende Diagramm, in dem der Partitionierungsprozess erläutert wird.
undefinierter Verweis auf Haupt-C ++
Das obige Diagramm zeigt den Prozess der Partitionierung des Arrays durch wiederholtes Auswählen des letzten Elements im Array als Drehpunkt. Beachten Sie, dass wir das Array auf jeder Ebene in zwei Unterarrays aufteilen, indem wir den Pivot an der richtigen Position platzieren.
Als nächstes listen wir den Algorithmus und den Pseudocode für die Quicksort-Technik auf, die auch die Partitionsroutine enthält.
Quicksort-Algorithmus Java
Der allgemeine Algorithmus für die Quicksortierung ist unten angegeben.
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low Unten ist der Pseudocode für die Quicksort-Technik angegeben.
Pseudocode zum schnellen Sortieren
Es folgt der Pseudocode für eine schnelle Sortiertechnik. Beachten Sie, dass wir den Pseudocode für die Quicksortierungs- und Partitionierungsroutine bereitgestellt haben.
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low Illustration
Sehen wir uns die Abbildung des Quicksort-Algorithmus an. Nehmen Sie das folgende Array als Beispiel. Hier haben wir das letzte Element als Drehpunkt ausgewählt.
Wie gezeigt ist das erste Element als niedrig und das letzte Element als hoch gekennzeichnet.
Wie in der obigen Abbildung ersichtlich, gibt es zwei Zeiger, hoch und niedrig, die jeweils auf das letzte und das erste Element des Arrays zeigen. Diese beiden Zeiger werden im Verlauf der Quicksortierung verschoben.
Wenn das Element, auf das der niedrige Zeiger zeigt, größer als das Pivot-Element wird und das Element, auf das der hohe Zeiger zeigt, kleiner als das Pivot-Element ist, tauschen wir die Elemente aus, auf die der niedrige und der hohe Zeiger zeigen, und jeder Zeiger rückt um 1 Position vor.
Die obigen Schritte werden ausgeführt, bis sich beide Zeiger im Array kreuzen. Sobald sie sich kreuzen, erhält das Pivot-Element seine richtige Position im Array. Zu diesem Zeitpunkt ist das Array partitioniert, und jetzt können wir jedes Unterarray unabhängig sortieren, indem wir rekursiv einen schnellen Sortieralgorithmus auf jedes der Unterarrays anwenden.
Java, wie man ein Array sortiert
Quicksort-Implementierung in Java
Die QuickSort-Technik kann in Java entweder durch Rekursion oder Iteration implementiert werden. In diesem Abschnitt werden wir beide Techniken sehen.
Rekursives Quicksort
Wir wissen, dass die oben dargestellte grundlegende Technik des Quicksortierens eine Rekursion zum Sortieren des Arrays verwendet. In der rekursiven Quicksortierung nach der Partitionierung des Arrays wird die Quicksortroutine rekursiv aufgerufen, um die Unterarrays zu sortieren.
Die folgende Implementierung demonstriert die Quicksort-Technik mithilfe der Rekursion.
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j Ausgabe:
Ursprüngliches Array: (4, -1, 6, 8, 0, 5, -3)
Sortiertes Array: (-3, -1, 0, 4, 5, 6, 8)
Iterative Quicksort
In der iterativen Quicksortierung verwenden wir den Hilfsstapel, um Zwischenparameter zu platzieren, anstatt Rekursions- und Sortierpartitionen zu verwenden.
Das folgende Java-Programm implementiert iteratives Quicksort.
Java, wie man eine Warteschlange macht
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 Ausgabe:
Ursprüngliches Array: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Sortiertes Array: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)
Häufig gestellte Fragen
F # 1) Wie funktioniert ein Quicksort?
Antworten: Quicksort verwendet eine Divide and Conquers-Strategie. Quicksort partitioniert zuerst ein Array um ein ausgewähltes Pivot-Element und generiert Sub-Arrays, die rekursiv sortiert werden.
F # 2) Wie komplex ist Quicksort zeitlich?
Antworten: Die zeitliche Komplexität von Quicksort beträgt im Durchschnitt O (nlogn). Im schlimmsten Fall ist O (n ^ 2) dasselbe wie die Auswahlsortierung.
F # 3) Wo wird Quicksort verwendet?
Antworten: Quicksort wird hauptsächlich in rekursiven Anwendungen verwendet. Quicksort ist der Teil der C-Bibliothek. Außerdem implementieren fast alle Programmiersprachen, die eine integrierte Sortierung verwenden, Quicksort.
F # 4) Was ist der Vorteil von Quicksort?
Antworten:
- Quicksort ist ein effizienter Algorithmus und kann selbst eine große Liste von Elementen problemlos sortieren.
- Es ist eine In-Place-Sortierung und benötigt daher keinen zusätzlichen Speicherplatz oder Speicher.
- Es ist weit verbreitet und bietet eine effiziente Möglichkeit, Datensätze beliebiger Länge zu sortieren.
F # 5) Warum ist Quicksort besser als die Zusammenführungssortierung?
Antworten: Der Hauptgrund, aus dem die Quicksortierung besser ist als die Zusammenführungssortierung, besteht darin, dass die Quicksortierung eine direkte Sortiermethode ist und keinen zusätzlichen Speicherplatz benötigt. Die Zusammenführungssortierung erfordert zusätzlichen Speicher für die Zwischensortierung.
Fazit
Quicksort wird hauptsächlich aufgrund seiner Effizienz als bester Sortieralgorithmus angesehen, um selbst einen großen Datensatz in O (nlogn) -Zeit zu sortieren.
Quicksort ist ebenfalls eine direkte Sortierung und benötigt keinen zusätzlichen Speicherplatz. In diesem Tutorial haben wir die rekursive und iterative Implementierung von Quicksort gesehen.
In unserem nächsten Tutorial werden wir mit den Sortiermethoden in Java fortfahren.
=> Schauen Sie sich hier den Java Beginners Guide an.
Literatur-Empfehlungen
- Binärer Suchalgorithmus in Java - Implementierung und Beispiele
- Java Array - Wie drucke ich Elemente eines Arrays in Java?
- Auswahlsortierung in Java - Auswahlsortierungsalgorithmus und Beispiele
- Array-Datentypen - int Array, Double Array, Array of Strings usw.
- Java-Array - Deklarieren, Erstellen und Initialisieren eines Arrays in Java
- JAVA-Tutorial für Anfänger: Über 100 praktische Java-Video-Tutorials
- Java Copy Array: Kopieren / Klonen eines Arrays in Java
- Java Array Length Tutorial mit Codebeispielen
