QuickSort-Algorithmus

In diesem Tutorial erfahren Sie, wie Quicksort funktioniert. Außerdem finden Sie Arbeitsbeispiele für Quicksort in C, C ++ Python und Java.

Quicksort ist ein Algorithmus, der auf dem Divide and Conquer-Ansatz basiert, bei dem das Array in Subarrays aufgeteilt wird und diese Subarrays rekursiv aufgerufen werden, um die Elemente zu sortieren.

Wie funktioniert QuickSort?

  1. Aus dem Array wird ein Pivot-Element ausgewählt. Sie können ein beliebiges Element aus dem Array als Pivot-Element auswählen.
    Hier haben wir das am weitesten rechts stehende (dh das letzte Element) des Arrays als Pivot-Element verwendet. Wählen Sie ein Pivot-Element aus
  2. Die Elemente, die kleiner als das Pivot-Element sind, werden links und die Elemente, die größer als das Pivot-Element sind, werden rechts platziert. Platzieren Sie alle kleineren Elemente links und die größeren rechts vom Schwenkelement.
    Die obige Anordnung wird durch die folgenden Schritte erreicht.
    1. Ein Zeiger ist am Schwenkelement befestigt. Das Pivot-Element wird mit den Elementen ab dem ersten Index verglichen. Wenn das Element erreicht wird, das größer als das Pivot-Element ist, wird ein zweiter Zeiger für dieses Element gesetzt.
    2. Jetzt wird das Pivot-Element mit den anderen Elementen verglichen (ein dritter Zeiger). Wenn ein Element erreicht wird, das kleiner als das Pivot-Element ist, wird das kleinere Element gegen das zuvor gefundene größere Element ausgetauscht. Vergleich des Schwenkelements mit anderen Elementen
    3. Der Vorgang wird fortgesetzt, bis das vorletzte Element erreicht ist.
      Schließlich wird das Pivot-Element mit dem zweiten Zeiger ausgetauscht. Tauschen Sie das Pivot-Element mit dem zweiten Zeiger aus
    4. Nun werden die linken und rechten Unterteile dieses Pivot-Elements in den folgenden Schritten zur weiteren Verarbeitung verwendet.
  3. Pivot-Elemente werden wiederum für das linke und das rechte Unterteil getrennt ausgewählt. Innerhalb dieser Unterteile sind die Schwenkelemente an ihrer richtigen Position platziert. Dann wird Schritt 2 wiederholt. Wählen Sie das Schwenkelement in jeder Hälfte aus und platzieren Sie es mithilfe der Rekursion an der richtigen Stelle
  4. Die Unterteile werden wieder in kleinere Unterteile unterteilt, bis jedes Unterteil aus einem einzigen Element besteht.
  5. Zu diesem Zeitpunkt ist das Array bereits sortiert.

Quicksort verwendet die Rekursion zum Sortieren der Unterteile.

Auf der Grundlage des Divide and Conquer-Ansatzes kann der Quicksort-Algorithmus wie folgt erklärt werden:

  • Teilen
    Das Array ist in Unterteile unterteilt, die den Pivot als Partitionierungspunkt verwenden. Die Elemente, die kleiner als der Drehpunkt sind, werden links vom Drehpunkt platziert, und die Elemente, die größer als der Drehpunkt sind, werden rechts platziert.
  • Erobern
    Die linken und rechten Unterteile werden erneut mithilfe von Pivot-Elementen für sie unterteilt. Dies kann erreicht werden, indem die Unterteile rekursiv an den Algorithmus übergeben werden.
  • Kombinieren
    Dieser Schritt spielt beim Quicksortieren keine wesentliche Rolle. Das Array ist bereits am Ende des Eroberungsschritts sortiert.

Sie können die Funktionsweise von Quicksort anhand der folgenden Abbildungen verstehen.

Sortieren der Elemente links vom Pivot mithilfe der Rekursion Sortieren der Elemente rechts vom Pivot mithilfe der Rekursion

Schneller Sortieralgorithmus

 quickSort (Array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- Partition (Array, leftmostIndex, rightmostIndex) quickSort (Array, leftmostIndex, pivotIndex) quickSort (Array, PivotIndex + 1, rightmostIndex) ) setze rightmostIndex als pivotIndex storeIndex <- leftmostIndex - 1 für i <- leftmostIndex + 1 auf rightmostIndex, wenn Element (i) <pivotElement Swap-Element (i) und Element (storeIndex) storeIndex ++ swap pivotElement und Element (storeIndex + 1) storeIndex + zurückgeben 1

Beispiele für Python, Java und C / C ++

Python Java C C + 
 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)
 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )
 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Quicksort-Komplexität

Zeitliche Komplexität

  • Worst-Case-Komplexität (Big-O) : Sie tritt auf, wenn das ausgewählte Pivot-Element entweder das größte oder das kleinste Element ist. Dieser Zustand führt zu dem Fall, dass das Pivot-Element an einem äußersten Ende des sortierten Arrays liegt. Ein Unterarray ist immer leer und ein anderes Unterarray enthält Elemente. Daher wird Quicksort nur für dieses Subarray aufgerufen. Der schnelle Sortieralgorithmus bietet jedoch eine bessere Leistung für verstreute Drehpunkte.O(n2)
    n - 1

  • Best-Case-Komplexität (Big-Omega) : O(n*log n)
    Sie tritt auf, wenn das Pivot-Element immer das mittlere Element oder in der Nähe des mittleren Elements ist.
  • Durchschnittliche Fallkomplexität (Big-Theta) : O(n*log n)
    Sie tritt auf, wenn die oben genannten Bedingungen nicht erfüllt sind.

Raumkomplexität

Die Raumkomplexität für Quicksort ist O(log n).

Quicksort-Anwendungen

Quicksort wird implementiert, wenn

  • Die Programmiersprache ist gut für die Rekursion
  • Zeitkomplexität ist wichtig
  • Raumkomplexität ist wichtig

Interessante Beiträge...