Einführung in die schnellen Sortieralgorithmen in Java
Die schnelle Sortierung in Java, auch als Partition-Exchange-Sortierung bezeichnet, ist ein Sortieralgorithmus zum Teilen und Erobern. Die schnelle Sortierung ist ein gutes Beispiel für einen Algorithmus, bei dem CPU-Caches aufgrund ihrer Aufteilung und Eroberung optimal genutzt werden. Der Quicksort-Algorithmus ist einer der am häufigsten verwendeten Sortieralgorithmen, insbesondere zum Sortieren der großen Listen, und die meisten Programmiersprachen haben ihn implementiert. Beim Quicksort-Algorithmus werden die Originaldaten in zwei Teile unterteilt, die einzeln sortiert und dann zu sortierten Daten zusammengeführt werden.
Nehmen wir an, dass das Array (8, 6, 3, 4, 9, 2, 1, 7) mit der Funktion "Schnellsortierung" sortiert werden muss.
Schritte zum Implementieren von Algorithmen für die schnelle Sortierung
1. Wählen Sie ein Element namens Pivot aus dem Array. Im Allgemeinen wird das mittlere Element als Drehpunkt gewählt. Nehmen wir 4 als Drehpunkt.
2. Ordnen Sie das Array in zwei Teile um, sodass Elemente, die kleiner als der Drehpunkt sind, vor dem Drehpunkt und Elemente, die größer als der Drehpunkt sind, nach dem Drehpunkt angezeigt werden. Folgende Schritte werden ausgeführt:
- Wählen Sie das am weitesten links stehende Element aus, dh 8. Da 4 der Drehpunkt ist und 8 mehr als 4 ist, muss 8 nach rechts von 4 verschoben werden. Auf der rechten Seite verlassen wir 7, da es größer als 4 ist, und wählen 1 zum Vertauschen mit 8 ergibt sich nach dem Vertauschen das Array zu: 1, 6, 3, 4, 9, 2, 8, 7
- Wählen Sie das nächste linke Element aus, dh 6. Da 4 der Drehpunkt ist und 6 mehr als 4 ist, muss 6 nach rechts von 4 verschoben werden. Auf der rechten Seite verlassen wir 7, 8, da sie größer als 4 sind, und wählen 2 zum Tauschen mit 6, daher wird das Array nach dem Tauschen zu: 1, 2, 3, 4, 9, 6, 8, 7
- Da nun alle Elemente links vom Drehpunkt kleiner als der Drehpunkt sind und alle Elemente rechts vom Drehpunkt größer als der Drehpunkt sind, haben wir 4 als Drehpunkt.
3. Wenden Sie die Schritte 1 und 2 rekursiv für das linke Unterarray (Array mit Elementen, die kleiner als der Pivot sind) und für das rechte Unterarray (Array mit Elementen, die größer als der Pivot sind) an. Wenn das Array nur ein oder null Elemente enthält, wird das Array als sortiert betrachtet.
Programm zur Implementierung schneller Sortieralgorithmen
Hier ist ein Java-Programm zum Sortieren eines Arrays von ganzen Zahlen mit einem schnellen Sortieralgorithmus.
Code:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
Ausgabe:
Vorteile schneller Sortieralgorithmen
Das Folgende sind die Vorteile des schnellen Sortieralgorithmus:
- Ausgezeichnete Referenzlokalität: Die Referenzlokalität ist die Fähigkeit eines Prozessors, über einen kurzen Zeitraum wiederholt auf denselben Speicherort zuzugreifen. Das schnelle Sortieren in Java bietet aufgrund der sehr geringen Anzahl von Cache-Fehlern, die auf modernen Architekturen für die Leistung von entscheidender Bedeutung sind, eine hervorragende Referenzlokalität.
- Schnelle Sortierung ist parallelisierbar: Sobald der erste Schritt der Partitionierung eines Arrays in kleinere Regionen abgeschlossen ist, können alle einzelnen Subarrays unabhängig voneinander parallel sortiert werden. Aus diesem Grund ist die schnelle Sortierung besser.
Komplexitätsanalyse der schnellen Sortierung
Quicksort ist ein schneller und rekursiver Algorithmus, der nach dem Divisions- und Eroberungsprinzip arbeitet. Hier ist die Komplexitätsanalyse in Best, Average und Worst Case:
- Best-Case-Komplexität: Wenn ein Array oder eine Liste n Elemente enthält, benötigt der erste Lauf O (n). Das Sortieren der verbleibenden zwei Subarrays dauert nun 2 * O (n / 2). Damit ist die Komplexität von O (n logn) im besten Fall abgeschlossen.
- Durchschnittliche Fallkomplexität: Der durchschnittliche Fall von Quicksort ist O (n log n).
- Worst-Case-Komplexität: Die Auswahl von first oder last führt zu einer Worst-Case-Leistung für nahezu sortierte oder nahezu rückwärts sortierte Daten. Schnelle Sortierung führt im schlimmsten Fall O (n 2) aus.
In Java Arrays. Die Methode Sort () verwendet einen schnellen Sortieralgorithmus zum Sortieren eines Arrays.
Empfohlene Artikel
Dies ist eine Anleitung zu schnellen Sortieralgorithmen in Java. Hier diskutieren wir die Schritte zur Implementierung, die Vorteile und die Komplexitätsanalyse eines schnellen Sortieralgorithmus in Java zusammen mit dem Programm. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren -
- Einfügesortierung in Java
- do-while-Schleife in Java
- JComponent in Java
- Quadrate in Java
- In PHP tauschen
- Sortierung in C #
- Sortierung in Python
- C ++ Algorithmus | Beispiele für den C ++ - Algorithmus