Schnelle Sortieralgorithmen in Java

Schnellsortierung in Java, auch bekannt als Partition-Exchange-Sortierung, ist ein Divide-and-Conquer-Sortieralgorithmus. Die schnelle Sortierung ist ein gutes Beispiel für einen Algorithmus, der aufgrund seiner Divide-and-Conqueres-Natur am besten CPU-Caches nutzt. Der Quicksort-Algorithmus ist einer der am häufigsten verwendeten Sortieralgorithmen, insbesondere zum Sortieren großer Listen, und die meisten Programmiersprachen haben ihn implementiert. Der Quicksort-Algorithmus teilt die Originaldaten in zwei Teile: einzeln sortiert und dann zusammengeführt, um sortierte Daten zu erzeugen.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Nehmen wir an, dass das Array {8, 6, 3, 4, 9, 2, 1, 7} mit Quick Sort sortiert werden muss.

Schritte zur Implementierung von Schnellsortierungsalgorithmen

1. Wählen Sie aus dem Array ein Element namens Pivot aus. 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 Pivot sind, vor dem Pivot stehen und Elemente, die größer als der Pivot sind, nach dem Pivot erscheinen. Folgende Schritte werden befolgt:

• Wählen Sie das Element ganz links aus, d. h. 8; Da 4 der Drehpunkt ist und 8 mehr als 4 ist, muss 8 nach rechts von 4 verschoben werden. Auf der rechten Seite belassen wir 7, da es größer als 4 ist, und wählen 1 zum Austauschen mit 8 aus. Nach dem Austauschen wird das Array also zu: 1,6,3,4,9,2,8,7
• Wählen Sie das nächste linke Element, d. h. 6; Da 4 der Drehpunkt ist und 6 mehr als 4 ist, muss 6 nach rechts von 4 verschoben werden. Auf der rechten Seite belassen wir 7,8, da sie größer als 4 sind, und wählen 2 zum Austauschen mit 6 aus. Nach dem Austauschen wird das Array also zu: 1,2,3,4,9,6,8,7
• Da nun alle Elemente links vom Pivot kleiner als der Pivot und alle Elemente rechts vom Pivot größer als der Pivot sind, sind wir mit 4 als Pivot fertig.

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, gilt das Array als sortiert.

Programm zur Implementierung schneller Sortieralgorithmen

Hier ist ein Java-Programm zum Sortieren eines Arrays von Ganzzahlen mithilfe eines Schnellsortierungsalgorithmus.

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 von Schnellsortierungsalgorithmen

Das Folgende sind die Vorteile des Schnellsortierungsalgorithmus:

• Ausgezeichnete Referenzlokalität: Die Referenzlokalität ist die Fähigkeit eines Prozessors, über einen kurzen Zeitraum wiederholt auf denselben Speicherort zuzugreifen. Die schnelle Sortierung in Java bietet aufgrund der sehr geringen Anzahl von Cache-Fehlern, die auf modernen Architekturen entscheidend für die Leistung sind, eine hervorragende Referenzlokalität.
• Schnellsortierung ist parallelisierbar: Sobald der erste Schritt der Partitionierung eines Arrays in kleinere Bereiche abgeschlossen ist, können alle einzelnen Unterarrays unabhängig voneinander parallel sortiert werden. Aus diesem Grund ist die Schnellsortierung besser.

Komplexitätsanalyse der Schnellsortierung

Quicksort ist ein schneller und endrekursiver Algorithmus, der nach dem Divide-and-Conquer-Prinzip arbeitet. Hier ist die Komplexitätsanalyse im besten, durchschnittlichen und schlechtesten Fall:

• 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 erfordert 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 würde zu einer Worst-Case-Leistung für nahezu sortierte oder nahezu umgekehrt sortierte Daten führen. Die schnelle Sortierung führt im schlimmsten Fall zu O (n^2).

 In Java Arrays. Die Methode Sort () verwendet einen schnellen Sortieralgorithmus, um ein Array zu sortieren.

Das obige ist der detaillierte Inhalt vonSchnelle Sortieralgorithmen in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!