QuickSort ist ein Divide & Conquer-Algorithmus. Im Divide & Conquer-Algorithmus-Entwurfsparadigma teilen wir die Probleme rekursiv in Unterprobleme auf, lösen dann die Unterprobleme und kombinieren schließlich die Lösungen, um das Endergebnis zu finden. In diesem Artikel konzentrieren wir uns auf QuickSort In
Die folgenden Hinweise werden in diesem Artikel behandelt:
Lass uns anfangen!
Eine Sache, die bei der Aufteilung der Probleme in Unterprobleme zu beachten ist, ist, dass sich die Struktur der Unterprobleme gegenüber dem ursprünglichen Problem nicht ändert.
Der Divide & Conquer-Algorithmus besteht aus 3 Schritten:
- Teilen: Das Problem in Teilprobleme aufteilen
- Erobern: Rekursive Lösung der Teilprobleme
- Kombinieren: Kombinieren Sie die Lösungen, um das Endergebnis zu erhalten
Es gibt verschiedene Algorithmen, die auf dem Divide & Conquer-Paradigma basieren. Schnelle Sortierung und Zusammenführungssortierung gehören dazu.
Obwohl die Zeitkomplexität von QuickSort im ungünstigsten Fall O (n2) ist, was mehr als viele andere Sortieralgorithmen wie Merge Sort und Heap Sort ist, ist QuickSort in der Praxis schneller, da seine innere Schleife auf den meisten Architekturen und in den meisten effizient implementiert werden kann reale Daten.
Lassen Sie uns über die Implementierung des Schnellsortierungsalgorithmus sprechen. Quicksort-Algorithmen verwenden ein Pivot-Element und partitionieren das Array um das Pivot-Element. Es gibt eine Reihe von Variationen von Quicksot, die davon abhängen, wie Sie das Pivot-Element auswählen. Es gibt mehrere Möglichkeiten, das Pivot-Element auszuwählen:
- Das erste Element auswählen
- Wählen Sie das letzte Element
- Ein zufälliges Element auswählen
- Medianelement auswählen
Das nächste wichtige Element ist die Funktion partition () im Schnellsortieralgorithmus. Die Partitionsfunktion zum Aufnehmen eines Pivot-Elements platziert es an der richtigen Position, verschiebt alle Elemente, die kleiner als das Pivot-Element sind, nach links und alle Elemente nach rechts. Quicksort benötigt dafür lineare Zeit.
Dann wird das Array vom Pivot-Element in zwei Teile geteilt (d. H. Elemente kleiner als Pivot und Elemente größer als Pivot) und beide Arrays werden unter Verwendung des Quicksort-Algorithmus rekursiv sortiert.
wie man ein Ingenieur wird
Nachdem wir die Funktionsweise des QuickSort-Algorithmus verstanden haben. Lassen Sie uns verstehen, wie der Quicksort-Algorithmus in Java implementiert wird.
Schnelle Sorte Funktion:
/ * Bei der Quicksort-Funktion muss das Array mit dem niedrigsten und höchsten Index sortiert werden * /
void sort (int arr [], int lowIndex, int highIndex) {// Bis lowIndex = highIndex if (lowIndexSchauen wir uns nun den Partitionierungscode an, um zu verstehen, wie er funktioniert.
Partition Code
Im Partitionierungscode wählen wir das letzte Element als Pivot-Element aus. Wir durchlaufen das gesamte Array (d. H. In unserem Fall unter Verwendung der Variablen j). Wir verfolgen das letzte kleinste Element im Array (d. H. Unter Verwendung der Variablen i in unserem Fall). Wenn wir ein Element finden, das kleiner als der Drehpunkt ist, verschieben wir das Swap-Stromelement a [j] mit arr [i], andernfalls fahren wir weiter.
int partition (int arr [], int lowIndex, int highIndex) {// Das letzte Element als Pivot erstellen int pivot = arr [highIndex] // Mit i kleinere Elemente vom Pivot aus verfolgen int i = (lowIndex-1) für (int j = lowIndex jNachdem Sie die Quicksort- und Partitionsfunktion verstanden haben, lassen Sie uns einen kurzen Blick auf den vollständigen Code werfen
lerne Visual Studio zu benutzen
Schnelle Sorte Java Code
Klasse QuickSort {// Partitionsmethode int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) für (int j = lowIndex j// Sortiermethode
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Methode zum Drucken eines Arrays
statische Leere printArray (int arr []) {int n = arr.length für (int i = 0 i// Hauptmethode
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.Länge QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sortiertes Array') printArray (arr)}} Ausgabe:
Nachdem Sie das obige Java-Programm ausgeführt haben, haben Sie verstanden, wie QuickSort funktioniert und wie es in Java implementiert wird.Damit sind wir am Ende dieses Artikels über 'Quicksort in Java' angelangt. Wenn Sie mehr erfahren möchten,Besuche die von Edureka, einem vertrauenswürdigen Online-Lernunternehmen. Der Java J2EE- und SOA-Schulungs- und Zertifizierungskurs von Edureka wurde entwickelt, um Sie sowohl für Kern- als auch für fortgeschrittene Java-Konzepte sowie für verschiedene Java-Frameworks wie Hibernate & Spring zu schulen.
Hast du eine Frage an uns? Bitte erwähne es im Kommentarbereich dieses Blogs und wir werden uns so schnell wie möglich bei dir melden.