logo

TechCodeview

QuickSort – Självstudier för datastruktur och algoritmer

QuickSort är en sorteringsalgoritm baserad på Dela och erövra algoritm som väljer ett element som en pivot och delar upp den givna arrayen runt den plockade pivoten genom att placera pivoten i dess korrekta position i den sorterade arrayen.

Hur fungerar QuickSort?

Nyckelprocessen i quickSort är en dela() . Målet med partitioner är att placera pivoten (vilket element som helst kan väljas att vara en pivot) i dess korrekta position i den sorterade arrayen och placera alla mindre element till vänster om pivoten, och alla större element till höger om pivoten. .

Partitionering görs rekursivt på varje sida av pivoten efter att pivoten har placerats i rätt position och detta sorterar slutligen arrayen.



Hur Quicksort fungerar

Hur Quicksort fungerar

Linux gratis ipconfig
Rekommenderad praxis Snabbsortering Prova!

Val av pivot:

Det finns många olika val för att plocka pivoter.

  • Välj alltid det första elementet som en pivot .
  • Välj alltid det sista elementet som en pivot (implementerad nedan)
  • Välj ett slumpmässigt element som en pivot .
  • Välj mitten som pivot.

Partitionsalgoritm:

Logiken är enkel, vi utgår från elementet längst till vänster och håller reda på indexet för mindre (eller lika) element som i . Om vi ​​hittar ett mindre element när vi korsar, byter vi det aktuella elementet med arr[i]. Annars ignorerar vi det aktuella elementet.

Låt oss förstå hur partitionen och Quick Sort-algoritmen fungerar med hjälp av följande exempel:

Tänk på: arr[] = {10, 80, 30, 90, 40}.

amisha patel
  • Jämför 10 med pivoten och eftersom den är mindre än pivoten, arrangera den efter varandra.

Partition i QuickSort: Jämför pivot med 10

  • Jämför 80 med pivoten. Det är större än pivot.

Partition i QuickSort: Jämför pivot med 80

  • Jämför 30 med pivot. Det är mindre än pivot så ordna det därefter.

Partition i QuickSort: Jämför pivot med 30

  • Jämför 90 med pivoten. Den är större än pivoten.

Partition i QuickSort: Jämför pivot med 90

  • Placera pivoten i rätt läge.

Partition i QuickSort: Placera pivoten i rätt position

Illustration av Quicksort:

Eftersom partitionsprocessen görs rekursivt, fortsätter den att placera pivoten i sin faktiska position i den sorterade arrayen. Att upprepade gånger sätta pivoter i deras faktiska position gör att arrayen sorteras.

Följ bilderna nedan för att förstå hur den rekursiva implementeringen av partitionsalgoritmen hjälper till att sortera arrayen.

java fall uttalande
  • Initial partition på huvudmatrisen:

Quicksort: Utför partitionen

  • Partitionering av subarrayerna:

Quicksort: Utför partitionen

Kodimplementering av snabbsorteringen:

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 ska sorteras, // låg --> Startindex, // hög --> Slutindex 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>
Pytonorm 
# 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 ska sorteras, // låg --> Startindex, // hög --> Slutindex 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 ?>// Denna funktion tar det sista elementet som pivot // Placera pivoten som korrekt position // I Sortered Array, och placerar alla mindre till vänster // av pivot och alla större element till höger om pivotfunktionspartitionen(&$arr, $low,$high) { // Välj pivotelementet $pivot= $arr[$high]; // Index av mindre element och indikerar // Rätt position för pivot $i=($low-1); för($j=$låg;$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>
Produktion 
Sorted Array 1 5 7 8 9 10>

Komplexitetsanalys av snabbsortering :

Tidskomplexitet:

  • Bästa fall : Ω (N log (N))
    Det bästa scenariot för quicksort inträffar när pivoten som väljs vid varje steg delar upp arrayen i ungefär lika stora halvor.
    I det här fallet kommer algoritmen att skapa balanserade partitioner, vilket leder till effektiv sortering.
  • Genomsnittligt fall: θ ( N log (N))
    Quicksorts genomsnittliga fallprestanda är vanligtvis mycket bra i praktiken, vilket gör den till en av de snabbaste sorteringsalgoritmerna.
  • Värsta fall: O(N2)
    Det värsta scenariot för Quicksort inträffar när pivoten vid varje steg konsekvent resulterar i mycket obalanserade partitioner. När matrisen redan är sorterad och pivoten alltid väljs som det minsta eller största elementet. För att mildra det värsta scenariot används olika tekniker som att välja en bra pivot (t.ex. median av tre) och använda Randomized algoritm (Randomized Quicksort ) för att blanda elementet innan sortering.
  • Hjälputrymme: O(1), om vi inte tar hänsyn till det rekursiva stackutrymmet. Om vi ​​betraktar det rekursiva stackutrymmet då, i värsta fall skulle quicksort kunna göra O ( N ).

Fördelar med snabb sortering:

  • Det är en dela-och-härska-algoritm som gör det lättare att lösa problem.
  • Det är effektivt på stora datamängder.
  • Den har en låg omkostnad, eftersom den bara kräver en liten mängd minne för att fungera.

Nackdelar med snabb sortering:

  • Den har en tidskomplexitet i värsta fall av O(N2), vilket inträffar när pivoten är dåligt vald.
  • Det är inte ett bra val för små datamängder.
  • Det är inte en stabil sortering, vilket innebär att om två element har samma nyckel, kommer deras relativa ordning inte att bevaras i den sorterade utgången vid snabb sortering, eftersom vi här byter element enligt pivotens position (utan att beakta deras ursprungliga positioner).