Snel sorteren is een sorteeralgoritme gebaseerd op de Verdeel en heers-algoritme dat een element als draaipunt kiest en de gegeven array rond het gekozen draaipunt verdeelt door het draaipunt op de juiste positie in de gesorteerde array te plaatsen.
Hoe werkt QuickSort?
Aanbevolen praktijk Snel sorteren Probeer het!Het sleutelproces in Snel sorteren is een partitie() . Het doel van partities is om het draaipunt (elk element kan als draaipunt worden gekozen) op de juiste positie in de gesorteerde array te plaatsen en alle kleinere elementen links van het draaipunt te plaatsen, en alle grotere elementen rechts van het draaipunt. .
De verdeling gebeurt recursief aan elke kant van het draaipunt nadat het draaipunt in de juiste positie is geplaatst en dit sorteert uiteindelijk de array.
Hoe Quicksort werkt
java mvc
Keuze van draaipunt:
Er zijn veel verschillende keuzes voor het kiezen van draaipunten.
- Kies altijd het eerste element als draaipunt .
- Kies altijd het laatste element als draaipunt (hieronder geïmplementeerd)
- Kies een willekeurig element als draaipunt .
- Kies het midden als draaipunt.
Partitie-algoritme:
De logica is eenvoudig, we beginnen met het meest linkse element en houden de index van kleinere (of gelijke) elementen bij i . Als we tijdens het doorlopen een kleiner element vinden, verwisselen we het huidige element met arr[i]. Anders negeren we het huidige element.
Laten we de werking van partitie en het Quick Sort-algoritme begrijpen met behulp van het volgende voorbeeld:
Beschouw: arr[] = {10, 80, 30, 90, 40}.
- Vergelijk 10 met het draaipunt en plaats het overeenkomstig.
Partitie in QuickSort: Vergelijk pivot met 10
- Vergelijk 80 met het draaipunt. Het is groter dan een draaipunt.
Partitie in QuickSort: Vergelijk pivot met 80
Java snijden
- Vergelijk 30 met draaipunt. Het is minder dan een draaipunt, dus regel het dienovereenkomstig.
Partitie in QuickSort: Vergelijk pivot met 30
- Vergelijk 90 met het draaipunt. Het is groter dan het draaipunt.
Partitie in QuickSort: Vergelijk pivot met 90
- Plaats het draaipunt in de juiste positie.
Partitie in QuickSort: Plaats het draaipunt in de juiste positie
Illustratie van Quicksort:
Omdat het partitieproces recursief wordt uitgevoerd, blijft het draaipunt in de werkelijke positie in de gesorteerde array staan. Door de draaipunten herhaaldelijk in hun werkelijke positie te plaatsen, wordt de array gesorteerd.
Volg de onderstaande afbeeldingen om te begrijpen hoe de recursieve implementatie van het partitie-algoritme helpt bij het sorteren van de array.
lijst met religies
- Initiële partitie op de hoofdarray:
Quicksort: Het uitvoeren van de partitie
- Partitionering van de subarrays:
Quicksort: Het uitvoeren van de partitie
Code-implementatie van de Quick Sort:
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 // 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[] -->Array die moet worden gesorteerd, // laag --> Beginindex, // hoog --> Eindindex static void quickSort(int[] arr, int low, int high) { if (laag< 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# // 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[] -->Array die moet worden gesorteerd, // laag --> Beginindex, // hoog --> Eindindex static void quickSort(int[] arr, int low, int high) { if (laag< 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 ?>// Deze functie vindt plaats als laatste element als draaipunt // Plaats het draaipunt op de juiste positie // In gesorteerde array, en plaatst alle kleinere naar links // van het draaipunt en alle grotere elementen rechts van de draaifunctiepartitie(&$arr, $low,$high) {/ // Kies het draaielement $pivot= $arr[$high]; // Index van kleiner element en geeft aan // De juiste positie van pivot $i=($low-1); for($j=$laag;$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> Uitvoer
Sorted Array 1 5 7 8 9 10>
Complexiteitsanalyse van snel sorteren :
Tijdcomplexiteit:
- Beste geval : Ω (N log (N))
Het beste scenario voor quicksort doet zich voor wanneer het bij elke stap gekozen draaipunt de array in ongeveer gelijke helften verdeelt.
In dit geval zal het algoritme gebalanceerde partities maken, wat leidt tot efficiënt sorteren. - Gemiddeld geval: θ (N log (N))
De gemiddelde prestaties van Quicksort zijn in de praktijk meestal erg goed, waardoor het een van de snelste sorteeralgoritmen is. - Slechtste geval: O(N2)
Het slechtste scenario voor Quicksort doet zich voor wanneer het draaipunt bij elke stap consistent resulteert in zeer ongebalanceerde partities. Wanneer de array al is gesorteerd en het draaipunt altijd als het kleinste of grootste element wordt gekozen. Om het worstcasescenario te verzachten, worden verschillende technieken gebruikt, zoals het kiezen van een goede pivot (bijvoorbeeld de mediaan van drie) en het gebruik van een gerandomiseerd algoritme (Randomized Quicksort ) om het element in willekeurige volgorde af te spelen voordat het wordt gesorteerd. - Hulpruimte: O(1), als we geen rekening houden met de recursieve stapelruimte. Als we rekening houden met de recursieve stapelruimte, zou quicksort in het ergste geval kunnen maken O ( N ).
Voordelen van snel sorteren:
- Het is een verdeel-en-heers-algoritme dat het gemakkelijker maakt om problemen op te lossen.
- Het is efficiënt bij grote datasets.
- Het heeft een lage overhead, omdat het slechts een kleine hoeveelheid geheugen nodig heeft om te functioneren.
Nadelen van snel sorteren:
- Het heeft in het slechtste geval een tijdscomplexiteit van O(N2), wat optreedt wanneer het draaipunt slecht wordt gekozen.
- Het is geen goede keuze voor kleine datasets.
- Het is geen stabiele sortering, wat betekent dat als twee elementen dezelfde sleutel hebben, hun relatieve volgorde niet behouden blijft in de gesorteerde uitvoer in het geval van een snelle sortering, omdat we hier elementen verwisselen op basis van de positie van het draaipunt (zonder rekening te houden met hun oorspronkelijke sortering). posities).