QUICKSORT – TUTORIALS ZU DATENSTRUKTUR UND ALGORITHMUS

Schnelle Sorte ist ein Sortieralgorithmus, der auf dem basiert Divide-and-Conquer-Algorithmus Dadurch wird ein Element als Pivot ausgewählt und das angegebene Array um den ausgewählten Pivot herum aufgeteilt, indem der Pivot an der richtigen Position im sortierten Array platziert wird.

Wie funktioniert QuickSort?

Der Schlüsselprozess in schnelle Sorte ist ein Partition() . Das Ziel von Partitionen besteht darin, den Pivot (jedes Element kann als Pivot ausgewählt werden) an der richtigen Position im sortierten Array zu platzieren und alle kleineren Elemente links vom Pivot und alle größeren Elemente rechts vom Pivot zu platzieren .

Die Partitionierung erfolgt rekursiv auf jeder Seite des Pivots, nachdem der Pivot an der richtigen Position platziert wurde, wodurch das Array schließlich sortiert wird.

So funktioniert Quicksort
Mission Impossible alle Filme

Empfohlene Übung Schnellsortierung Probieren Sie es aus!

Wahl des Drehpunktes:

Es gibt viele verschiedene Möglichkeiten, Pivots auszuwählen.

Wählen Sie immer das erste Element als Drehpunkt .
Wählen Sie immer das letzte Element als Pivot (unten implementiert)
Wählen Sie ein zufälliges Element als Drehpunkt .
Wählen Sie die Mitte als Dreh- und Angelpunkt.

Partitionsalgorithmus:

Die Logik ist einfach: Wir beginnen mit dem Element ganz links und verfolgen den Index kleinerer (oder gleicher) Elemente als ich . Wenn wir beim Durchlaufen ein kleineres Element finden, tauschen wir das aktuelle Element mit arr[i] aus. Andernfalls ignorieren wir das aktuelle Element.

Lassen Sie uns die Funktionsweise der Partition und des Quick Sort-Algorithmus anhand des folgenden Beispiels verstehen:

Bedenken Sie: arr[] = {10, 80, 30, 90, 40}.

Vergleichen Sie 10 mit dem Drehpunkt und ordnen Sie ihn entsprechend an, da er kleiner als der Drehpunkt ist.

Partition in QuickSort: Pivot mit 10 vergleichen

Vergleichen Sie 80 mit dem Pivot. Es ist größer als Pivot.

Partition in QuickSort: Pivot mit 80 vergleichen
np std

Vergleichen Sie 30 mit Pivot. Es ist kleiner als der Drehpunkt, also ordnen Sie es entsprechend an.

Partition in QuickSort: Pivot mit 30 vergleichen

Vergleichen Sie 90 mit dem Pivot. Es ist größer als der Drehpunkt.

Partition in QuickSort: Pivot mit 90 vergleichen

Ordnen Sie den Drehpunkt in der richtigen Position an.

Partition in QuickSort: Pivot an der richtigen Position platzieren

Abbildung von Quicksort:

Da der Partitionierungsprozess rekursiv erfolgt, wird der Pivot immer wieder an seiner tatsächlichen Position im sortierten Array platziert. Durch wiederholtes Setzen von Pivots in ihre tatsächliche Position wird das Array sortiert.

Befolgen Sie die folgenden Bilder, um zu verstehen, wie die rekursive Implementierung des Partitionsalgorithmus beim Sortieren des Arrays hilft.

Java-Case-Anweisung

Erste Partition auf dem Hauptarray:

Quicksort: Durchführen der Partitionierung

Partitionierung der Subarrays:

Quicksort: Durchführen der Partitionierung

Code-Implementierung der Schnellsortierung:

C++

 #include  using namespace std; int partition(int arr[],int low,int high) {  //choose the pivot    int pivot=arr[high];  //Index of smaller element and Indicate  //the right position of pivot found so far  int i=(low-1);    for(int j=low;j<=high-1;j++)  {  //If current element is smaller than the pivot  if(arr[j]

 // C program for QuickSort #include  // Utility function to swap tp integers void swap(int* p1, int* p2) {  int temp;  temp = *p1;  *p1 = *p2;  *p2 = temp; } int partition(int arr[], int low, int high) {  // choose the pivot  int pivot = arr[high];  // Index of smaller element and Indicate  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(&arr[i], &arr[j]);  }  }  swap(&arr[i + 1], &arr[high]);  return (i + 1); } // The Quicksort function Implement void quickSort(int arr[], int low, int high) {  // when low is less than high  if (low < high) {  // pi is the partition return index of pivot  int pi = partition(arr, low, high);  // Recursion Call  // smaller element than pivot goes left and  // higher element goes right  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  } } int main() {  int arr[] = { 10, 7, 8, 9, 1, 5 };  int n = sizeof(arr) / sizeof(arr[0]);    // Function call  quickSort(arr, 0, n - 1);    // Print the sorted array  printf('Sorted Array
');  for (int i = 0; i < n; i++) {  printf('%d ', arr[i]);  }  return 0; } // This Code is Contributed By Diwakar Jha>

Java

 // Java implementation of QuickSort import java.io.*; class GFG {  // A utility function to swap two elements  static void swap(int[] arr, int i, int j)  {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // This function takes last element as pivot,  // places the pivot element at its correct position  // in sorted array, and places all smaller to left  // of pivot and all greater elements to right of pivot  static int partition(int[] arr, int low, int high)  {  // Choosing the pivot  int pivot = arr[high];  // Index of smaller element and indicates  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(arr, i, j);  }  }  swap(arr, i + 1, high);  return (i + 1);  }  // The main function that implements QuickSort  // arr[] -->Zu sortierendes Array, // niedrig --> Startindex, // hoch --> Endindex static void quickSort(int[] arr, int low, int high) { if (low< high) {  // pi is partitioning index, arr[p]  // is now at right place  int pi = partition(arr, low, high);  // Separately sort elements before  // partition and after partition  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  }  // To print sorted array  public static void printArr(int[] arr)  {  for (int i = 0; i < arr.length; i++) {  System.out.print(arr[i] + ' ');  }  }  // Driver Code  public static void main(String[] args)  {  int[] arr = { 10, 7, 8, 9, 1, 5 };  int N = arr.length;  // Function call  quickSort(arr, 0, N - 1);  System.out.println('Sorted array:');  printArr(arr);  } } // This code is contributed by Ayush Choudhary // Improved by Ajay Virmoti>

Python

 # Python3 implementation of QuickSort # Function to find the partition position def partition(array, low, high): # Choose the rightmost element as pivot pivot = array[high] # Pointer for greater element i = low - 1 # Traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # If element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # Swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # Swap the pivot element with # the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # Return the position from where partition is done return i + 1 # Function to perform quicksort def quicksort(array, low, high): if low < high: # Find pivot element such that # element smaller than pivot are on the left # element greater than pivot are on the right pi = partition(array, low, high) # Recursive call on the left of pivot quicksort(array, low, pi - 1) # Recursive call on the right of pivot quicksort(array, pi + 1, high) # Driver code if __name__ == '__main__': array = [10, 7, 8, 9, 1, 5] N = len(array) # Function call quicksort(array, 0, N - 1) print('Sorted array:') for x in array: print(x, end=' ') # This code is contributed by Adnan Aliakbar>

 // C# implementation of QuickSort using System; class GFG {  // A utility function to swap two elements  static void swap(int[] arr, int i, int j)  {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  // This function takes last element as pivot,  // places the pivot element at its correct position  // in sorted array, and places all smaller to left  // of pivot and all greater elements to right of pivot  static int partition(int[] arr, int low, int high)  {  // Choosing the pivot  int pivot = arr[high];  // Index of smaller element and indicates  // the right position of pivot found so far  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  swap(arr, i, j);  }  }  swap(arr, i + 1, high);  return (i + 1);  }  // The main function that implements QuickSort  // arr[] -->Zu sortierendes Array, // niedrig --> Startindex, // hoch --> Endindex static void quickSort(int[] arr, int low, int high) { if (low< high) {  // pi is partitioning index, arr[p]  // is now at right place  int pi = partition(arr, low, high);  // Separately sort elements before  // and after partition index  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  }  // Driver Code  public static void Main()  {  int[] arr = { 10, 7, 8, 9, 1, 5 };  int N = arr.Length;  // Function call  quickSort(arr, 0, N - 1);  Console.WriteLine('Sorted array:');  for (int i = 0; i < N; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by gfgking>

JavaScript

 // Function to partition the array and return the partition index function partition(arr, low, high) {  // Choosing the pivot  let pivot = arr[high];    // Index of smaller element and indicates the right position of pivot found so far  let i = low - 1;    for (let j = low; j <= high - 1; j++) {  // If current element is smaller than the pivot  if (arr[j] < pivot) {  // Increment index of smaller element  i++;  [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements  }  }    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position  return i + 1; // Return the partition index } // The main function that implements QuickSort function quickSort(arr, low, high) {  if (low < high) {  // pi is the partitioning index, arr[pi] is now at the right place  let pi = partition(arr, low, high);    // Separately sort elements before partition and after partition  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  } } // Driver code let arr = [10, 7, 8, 9, 1, 5]; let N = arr.length; // Function call quickSort(arr, 0, N - 1); console.log('Sorted array:'); console.log(arr.join(' '));>

PHP

  // code ?>// Diese Funktion übernimmt das letzte Element als Pivot // Platziert den Pivot an der richtigen Position // Im sortierten Array und platziert alle kleineren // links vom Pivot und alle größeren Elemente rechts von der Pivotfunktion partition(&$arr, $low,$high) { // Wählen Sie das Pivot-Element $pivot= $arr[$high]; // Index des kleineren Elements und gibt // die richtige Position des Pivots an $i=($low-1); for($j=$low;$j<=$high-1;$j++) { if($arr[$j]<$pivot) { // Increment index of smaller element $i++; list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]); } } // Pivot element as correct position list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]); return ($i+1); } // The main function that implement as QuickSort // arr[]:- Array to be sorted // low:- Starting Index //high:- Ending Index function quickSort(&$arr,$low,$high) { if($low<$high) { // pi is partition $pi= partition($arr,$low,$high); // Sort the array // Before the partition of Element quickSort($arr,$low,$pi-1); // After the partition Element quickSort($arr,$pi+1,$high); } } // Driver Code $arr= array(10,7,8,9,1,5); $N=count($arr); // Function Call quickSort($arr,0,$N-1); echo 'Sorted Array:
'; for($i=0;$i<$N;$i++) { echo $arr[$i]. ' '; } //This code is contributed by Diwakar Jha>

Ausgabe

Sorted Array 1 5 7 8 9 10>

Komplexitätsanalyse der Schnellsortierung :

Zeitkomplexität:

I'm besten fall : Ω (N log (N))
Das beste Szenario für Quicksort liegt vor, wenn der bei jedem Schritt gewählte Pivot das Array in ungefähr gleiche Hälften teilt.
In diesem Fall erstellt der Algorithmus ausgeglichene Partitionen, was zu einer effizienten Sortierung führt.
Durchschnittlicher Fall: θ ( N log (N))
Die durchschnittliche Fallleistung von Quicksort ist in der Praxis normalerweise sehr gut, was es zu einem der schnellsten Sortieralgorithmen macht.
Schlimmster Fall: O(N2)
Das Worst-Case-Szenario für Quicksort tritt auf, wenn der Pivot bei jedem Schritt durchgängig zu stark unausgeglichenen Partitionen führt. Wenn das Array bereits sortiert ist und der Pivot immer als kleinstes oder größtes Element ausgewählt wird. Um das Worst-Case-Szenario abzumildern, werden verschiedene Techniken verwendet, wie z. B. die Auswahl eines guten Pivots (z. B. der Median von drei) und die Verwendung eines randomisierten Algorithmus (Randomized Quicksort), um das Element vor dem Sortieren zu mischen.
Hilfsraum: O(1), wenn wir den rekursiven Stapelraum nicht berücksichtigen. Wenn wir den rekursiven Stapelplatz berücksichtigen, könnte Quicksort im schlimmsten Fall ausreichen Ö ( N ).

Vorteile der Schnellsortierung:

Es handelt sich um einen Divide-and-Conquer-Algorithmus, der die Lösung von Problemen erleichtert.
Es ist effizient bei großen Datenmengen.
Der Overhead ist gering, da für die Funktion nur wenig Speicher erforderlich ist.

Nachteile der Schnellsortierung:

Die Zeitkomplexität beträgt im ungünstigsten Fall O(N).²), was auftritt, wenn der Drehpunkt schlecht gewählt ist.
Für kleine Datensätze ist dies keine gute Wahl.
Es handelt sich nicht um eine stabile Sortierung, d. h. wenn zwei Elemente denselben Schlüssel haben, bleibt ihre relative Reihenfolge im Falle einer schnellen Sortierung nicht in der sortierten Ausgabe erhalten, da wir hier Elemente entsprechend der Position des Pivots austauschen (ohne Berücksichtigung ihres Originals). Positionen).

TechCodeview

QuickSort – Tutorials zu Datenstruktur und Algorithmen