QuickSort-algoritme

In deze tutorial leer je hoe quicksort werkt. Ook vindt u werkende voorbeelden van quicksort in C, C ++ Python en Java.

Quicksort is een algoritme gebaseerd op de verdeel en heersbenadering waarbij de array wordt opgesplitst in subarrays en deze sub-arrays recursief worden aangeroepen om de elementen te sorteren.

Hoe QuickSort werkt?

  1. Uit de array wordt een scharnierelement gekozen. U kunt elk element uit de array kiezen als het draai-element.
    Hier hebben we het meest rechtse (dwz het laatste element) van de array als het pivot-element genomen. Selecteer een draai-element
  2. De elementen kleiner dan het scharnierelement worden links geplaatst en de elementen groter dan het scharnierelement worden rechts geplaatst. Zet alle kleinere elementen aan de linkerkant en grotere aan de rechterkant van het scharnierelement.
    De bovenstaande opstelling wordt bereikt door de volgende stappen.
    1. Een wijzer is vastgezet op het scharnierelement. Het scharnierelement wordt vergeleken met de elementen beginnend bij de eerste index. Als het element groter dan het pivot-element wordt bereikt, wordt een tweede pointer voor dat element ingesteld.
    2. Nu wordt het pivot-element vergeleken met de andere elementen (een derde pointer). Als een element kleiner dan het scharnierelement wordt bereikt, wordt het kleinere element verwisseld met het grotere element dat eerder is gevonden. Vergelijking van spilelement met andere elementen
    3. Het proces gaat door totdat het voorlaatste element is bereikt.
      Ten slotte wordt het scharnierelement verwisseld met de tweede wijzer. Verwissel het draaipunt met de tweede aanwijzer
    4. Nu worden de linker en rechter subdelen van dit scharnierelement genomen voor verdere verwerking in de onderstaande stappen.
  3. Zwenkelementen worden wederom voor de linker en rechter subdelen afzonderlijk gekozen. Binnen deze subdelen zijn de zwenkelementen op hun juiste positie geplaatst. Vervolgens wordt stap 2 herhaald. Selecteer het draaipunt van elke helft en zet het op de juiste plaats door middel van recursie
  4. De subdelen worden weer opgedeeld in kleinere subdelen totdat elk subdeel uit een enkel element is gevormd.
  5. Op dit punt is de array al gesorteerd.

Quicksort gebruikt recursie voor het sorteren van de subonderdelen.

Op basis van de Divide and heers-aanpak kan het quicksort-algoritme worden uitgelegd als:

  • Verdelen
    De array is onderverdeeld in subdelen waarbij het draaipunt het verdelingspunt is. De elementen kleiner dan het draaipunt worden links van het draaipunt geplaatst en de elementen groter dan het draaipunt naar rechts.
  • Veroveren
    De linker en rechter subdelen worden weer opgedeeld met behulp van de door er pivot elementen voor te selecteren. Dit kan worden bereikt door de subdelen recursief in het algoritme door te geven.
  • Combineren
    Deze stap speelt bij quicksort geen rol van betekenis. De array is al gesorteerd aan het einde van de veroveringsstap.

Aan de hand van onderstaande afbeeldingen kunt u de werking van quicksort begrijpen.

De elementen links van het draaipunt sorteren met behulp van recursie De elementen rechts van het draaipunt sorteren met behulp van recursie

Snel sorteeralgoritme

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightxmostIndex) ) stel rightmostIndex in als pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) en element (storeIndex) storeIndex ++ swap pivotElement en element (storeIndex + 1) retourneren storeIndex + 1

Python, Java en C / C ++ voorbeelden

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-complexiteit

Tijdscomplexiteit

  • Worst Case Complexity (Big-O) : het treedt op wanneer het gekozen pivot-element het grootste of het kleinste element is. Deze voorwaarde leidt tot het geval waarin het scharnierelement in een uiterste uiteinde van de gesorteerde reeks ligt. Een sub-array is altijd leeg en een andere sub-array bevat elementen. Quicksort wordt dus alleen op deze subarray aangeroepen. Het snelle sorteeralgoritme heeft echter betere prestaties voor verspreide draaipunten.O(n2)
    n - 1

  • Best Case Complexity (Big-omega) : O(n*log n)
    het treedt op wanneer het scharnierelement altijd het middelste element of dicht bij het middelste element is.
  • Gemiddelde casuscomplexiteit (Big-theta) : O(n*log n)
    treedt op wanneer de bovenstaande omstandigheden niet voorkomen.

Complexiteit van de ruimte

De ruimtecomplexiteit voor quicksort is O(log n).

Quicksort-toepassingen

Quicksort wordt geïmplementeerd wanneer

  • de programmeertaal is goed voor recursie
  • tijdcomplexiteit is belangrijk
  • de complexiteit van de ruimte is belangrijk

Interessante artikelen...