QuickSort er en sorteringsalgoritme basert på Divide and Conquer-algoritmen som velger et element som en pivot og deler den gitte matrisen rundt den valgte pivoten ved å plassere pivoten i sin riktige posisjon i den sorterte matrisen.
Hvordan fungerer QuickSort?
Anbefalt praksis Hurtigsortering Prøv det!Nøkkelprosessen i quickSort er en skillevegg() . Målet med partisjoner er å plassere pivoten (hvilket som helst element kan velges til å være en pivot) på riktig posisjon i den sorterte matrisen og plassere alle mindre elementer til venstre for pivoten, og alle større elementer til høyre for pivoten. .
Partisjonen gjøres rekursivt på hver side av pivoten etter at pivoten er plassert i riktig posisjon, og dette sorterer til slutt matrisen.
Hvordan Quicksort fungerer
java parse streng til int
Valg av pivot:
Det er mange forskjellige valg for å plukke pivoter.
- Velg alltid det første elementet som en pivot .
- Velg alltid det siste elementet som en pivot (implementert nedenfor)
- Velg et tilfeldig element som pivot .
- Velg midten som pivot.
Partisjonsalgoritme:
Logikken er enkel, vi starter fra elementet lengst til venstre og holder styr på indeksen til mindre (eller like) elementer som Jeg . Mens vi krysser, hvis vi finner et mindre element, bytter vi det gjeldende elementet med arr[i]. Ellers ignorerer vi det gjeldende elementet.
La oss forstå hvordan partisjonen og Quick Sort-algoritmen fungerer ved hjelp av følgende eksempel:
Tenk på: arr[] = {10, 80, 30, 90, 40}.
til strengmetoden java
- Sammenlign 10 med pivot og som det er mindre enn pivot, ordne det i samsvar.
Partisjon i QuickSort: Sammenlign pivot med 10
- Sammenlign 80 med pivoten. Det er større enn pivot.
Partisjon i QuickSort: Sammenlign pivot med 80
- Sammenlign 30 med pivot. Det er mindre enn pivot så ordne det deretter.
Partisjon i QuickSort: Sammenlign pivot med 30
- Sammenlign 90 med pivoten. Den er større enn pivoten.
Partisjon i QuickSort: Sammenlign pivot med 90
- Plasser pivoten i riktig posisjon.
Partisjon i QuickSort: Plasser pivot i riktig posisjon
Illustrasjon av Quicksort:
Ettersom partisjonsprosessen gjøres rekursivt, fortsetter den å sette pivoten i sin faktiske posisjon i den sorterte matrisen. Ved å sette pivoter gjentatte ganger i deres faktiske posisjon blir matrisen sortert.
Følg bildene nedenfor for å forstå hvordan den rekursive implementeringen av partisjonsalgoritmen hjelper til med å sortere matrisen.
strenghåndtering i c++
- Innledende partisjon på hovedmatrisen:
Quicksort: Utfører partisjonen
- Partisjonering av undermatrisene:
Quicksort: Utfører partisjonen
Kodeimplementering av hurtigsortering:
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 som skal sorteres, // lav --> Startindeks, // høy --> Sluttindeks statisk void quickSort(int[] arr, int lav, int høy) { 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# // 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 som skal sorteres, // lav --> Startindeks, // høy --> Sluttindeks statisk void quickSort(int[] arr, int lav, int høy) { 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 ?>// Denne funksjonen finner sted siste element som pivot // Plasser pivoten som riktig posisjon // I Sortert Array, og plasserer alle mindre til venstre // av pivot og alle større element til høyre for pivotfunksjonspartisjonen(&$arr, $low,$high) { // Velg pivotelementet $pivot= $arr[$high]; // Indeks av mindre element og indikerer // Høyre posisjon til pivot $i=($low-1); for($j=$lav;$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> Produksjon
Sorted Array 1 5 7 8 9 10>
Kompleksitetsanalyse av rask sortering :
Tidskompleksitet:
- Beste sak : Ω (N log (N))
Det beste scenariet for quicksort oppstår når pivoten valgt ved hvert trinn deler matrisen i omtrent like halvdeler.
I dette tilfellet vil algoritmen lage balanserte partisjoner, noe som fører til effektiv sortering. - Gjennomsnittlig sak: θ ( N log (N))
Quicksorts gjennomsnittlige saksytelse er vanligvis veldig god i praksis, noe som gjør den til en av de raskeste sorteringsalgoritmene. - Verste tilfelle: O(N2)
Det verste scenariet for Quicksort oppstår når pivoten ved hvert trinn konsekvent resulterer i svært ubalanserte partisjoner. Når matrisen allerede er sortert og pivoten alltid velges som det minste eller største elementet. For å redusere det verste scenariet, brukes ulike teknikker som å velge en god pivot (f.eks. median på tre) og bruke randomisert algoritme (Randomized Quicksort ) for å blande elementet før sortering. - Hjelpeplass: O(1), hvis vi ikke vurderer det rekursive stabelrommet. Hvis vi vurderer den rekursive stabelplassen da, i verste fall kan quicksort gjøre O ( N ).
Fordeler med hurtigsortering:
- Det er en del-og-hersk-algoritme som gjør det lettere å løse problemer.
- Det er effektivt på store datasett.
- Den har lav overhead, da den bare krever en liten mengde minne for å fungere.
Ulemper med hurtigsortering:
- Den har en verste fall tidskompleksitet på O(N2), som oppstår når pivoten er dårlig valgt.
- Det er ikke et godt valg for små datasett.
- Det er ikke en stabil sortering, noe som betyr at hvis to elementer har samme nøkkel, vil deres relative rekkefølge ikke bli bevart i den sorterte utgangen i tilfelle rask sortering, fordi her bytter vi elementer i henhold til pivotens posisjon (uten å vurdere deres opprinnelige stillinger).