Einführung in Quick Sort in Java

Der folgende Artikel Schnelle Sortierung in Java enthält eine Übersicht über den Algorithmus für die schnelle Sortierung in Java. Der schnelle Sortieralgorithmus ist einer der Sortieralgorithmen, der effizient und dem des Mischsortieralgorithmus ähnlich ist. Dies ist einer der am häufigsten verwendeten Algorithmen für Sortierzwecke in Echtzeit. Die Zeitkomplexität im schlechtesten Fall dieses Algorithmus ist O (n 2), die Zeitkomplexität im durchschnittlichen Fall ist O (n log n) und die Zeitkomplexität im besten Fall ist O (n log n).

Die Raumkomplexität, wenn O (n log n) wobei n die Größe der Eingabe ist. Der Prozess des Sortierens umfasst das Partitionieren von Eingaben, rekursive Iterationen und das Markieren eines zentralen Elements für jede Rekursion. Die Art der Sortierung in diesem Algorithmus beinhaltet einen iterativen Vergleich benachbarter Elemente.

Wie funktioniert das schnelle Sortieren in Java?

Der Quick-Sort-Algorithmus kann in Java implementiert werden, indem ein Pseudocode mit einer Folge von Schritten gebildet wird, die auf effiziente Weise entworfen und befolgt werden.

  1. Das Hauptprinzip des Quick-Sort-Algorithmus basiert auf dem Divide-and-Conquer-Ansatz und ist auch ein effizienter Sortieralgorithmus.
  2. Das Eingabearray ist in Unterarrays unterteilt und die Unterteilung basiert auf dem Pivot-Element, das ein zentrales Element ist. Die Unterfelder auf beiden Seiten des Schwenkelements sind die Hauptbereiche, in denen die Sortierung tatsächlich stattfindet.
  3. Das zentrale Schwenkelement ist die Basis, um das Array in zwei Partitionen zu unterteilen, wobei die linke Hälfte der Arrayelemente kleiner als das Schwenkelement und die rechte Hälfte der Arrayelemente größer als das Schwenkelement ist.
  4. Bevor das Pivot-Element betrachtet wird, kann es sich um ein beliebiges Element aus einem Array handeln. Dies wird normalerweise zur Erleichterung des Verständnisses als mittleres oder erstes oder letztes angesehen. Das Pivot-Element kann ein zufälliges Element aus einem der Array-Elemente sein.
  5. In unserem Beispiel wird das letzte Element eines Arrays als Pivot-Element betrachtet, bei dem die Partitionierung von Unterarrays am rechten Ende des Arrays beginnt.
  6. Schließlich befindet sich das Schwenkelement nach Beendigung des Sortiervorgangs in seiner tatsächlich sortierten Position, wobei der Hauptsortiervorgang in der Partitionslogik des Sortieralgorithmus liegt.
  7. Die Effizienz des Algorithmus hängt von der Größe der Sub-Arrays und ihrer Verteilung ab. Je unausgeglichener die Sub-Arrays sind, desto größer ist die zeitliche Komplexität, die zur Komplexität im ungünstigsten Fall führt.
  8. Die zufällige Auswahl von Pivot-Elementen führt in vielen Fällen zu der bestmöglichen Zeitkomplexität, anstatt einen bestimmten Start-, End- oder Mittelindex als Pivot-Elemente zu wählen.

Beispiele zur Implementierung von Quick Sort in Java

Der QuickSort-Algorithmus wurde mit der folgenden Java-Programmiersprache implementiert, und der Ausgabecode wurde unter dem Code angezeigt.

  1. Der Code nimmt zunächst die Eingabe unter Verwendung der Methode quickSortAlgo () mit dem Array, dem Anfangsindex und dem Endindex, dh der Länge des Arrays, als Argumente entgegen.
  2. Nach dem Aufrufen der quickSortAlgo () -Methode wird überprüft, ob der Anfangsindex kleiner als der Endindex ist, und anschließend die arrayPartition () -Methode aufgerufen, um den Wert des Pivot-Elements abzurufen.
  3. Das Partitionselement enthält die Logik zum Anordnen der kleineren und größeren Elemente um das Pivot-Element basierend auf den Elementwerten.
  4. Nachdem die Methode quickSortAlgo () nach der Ausführung der Partitionsmethode den Pivot-Elementindex abgerufen hat, wird sie von sich aus rekursiv aufgerufen, bis alle Sub-Arrays vollständig partitioniert und sortiert sind.
  5. In der Partitionslogik wird das letzte Element als Pivot-Element zugewiesen und das erste Element mit dem Pivot-Element verglichen, dh dem letzten Element, bei dem die Elemente ausgetauscht werden, je nachdem, ob sie kleiner oder größer sind.
  6. Dieser Rekursionsprozess findet statt, bis alle Elemente eines Arrays partitioniert und sortiert sind, wobei das Endergebnis ein kombiniertes sortiertes Array ist.
  7. Die Elemente werden innerhalb der for-Loop-Iteration nur dann ausgetauscht, wenn das Element kleiner oder gleich dem Pivot-Element ist.
  8. Nach Abschluss des Iterationsprozesses wird das letzte Element ausgetauscht, dh der Wert des Pivot-Elements wird auf die linke Seite verschoben, sodass die neuen Partitionen erstellt und derselbe Prozess in Form einer Rekursion wiederholt wird, was zu einer Reihe von Sortiervorgängen für verschiedene mögliche Partitionen führt als Bildung von Subarrays aus den gegebenen Array-Elementen.
  9. Der folgende Code kann auf jeder IDE ausgeführt werden, und die Ausgabe kann überprüft werden, indem der Array-Wert in main () geändert wird. Die main-Methode wird nur zum Abrufen der Ausgabe in der Konsole verwendet. Als Teil der Java-Codierungsstandards kann die Hauptmethode unten entfernt und ein Objekt erstellt werden. Die Methoden unten können aufgerufen werden, indem sie nicht statisch gemacht werden.

Code-Implementierung des Quick-Sort-Algorithmus in Java

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)

Ausgabe:

Fazit

Der schnelle Sortieralgorithmus ist effizient, aber im Vergleich zu anderen Sortiertechniken nicht sehr stabil. Die Effizienz von Schnell-Sortier-Algorithmen nimmt ab, wenn mehr Elemente wiederholt werden, was ein Nachteil ist. Die Platzkomplexität wird in diesem schnellen Sortieralgorithmus optimiert.

Empfohlene Artikel

Dies ist eine Anleitung zum schnellen Sortieren in Java. Hier diskutieren wir, wie Quick Sort in Java funktioniert, zusammen mit einem Beispiel und der Implementierung von Code. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -

  1. Heap-Sortierung in Java
  2. Was ist ein binärer Baum in Java?
  3. Bit-Manipulation in Java
  4. Übersicht über die Zusammenführungssortierung in JavaScript
  5. Übersicht über die schnelle Sortierung in JavaScript
  6. Heap-Sortierung in Python
  7. Top 6 Sortieralgorithmus in JavaScript

Kategorie:

Software-Entwicklung