QUICKSORT - DATASTRUKTUR OG ALGORITMEVEJLEDNINGER - TECHCODEVIEW.COM

QuickSort er en sorteringsalgoritme baseret på Divide and Conquer-algoritme der vælger et element som et pivot og opdeler det givne array omkring det valgte pivot ved at placere pivoten i dens korrekte position i det sorterede array.

Hvordan virker QuickSort?

Nøgleprocessen i quickSort er en skillevæg() . Målet med partitioner er at placere pivoten (et hvilket som helst element kan vælges til at være en pivot) på dens korrekte position i det sorterede array og placere alle mindre elementer til venstre for pivoten og alle større elementer til højre for pivoten .

Opdelingen udføres rekursivt på hver side af pivoten, efter at pivoten er placeret i sin korrekte position, og dette sorterer til sidst arrayet.

Sådan fungerer Quicksort
prøv catch block i java

Anbefalet praksis Hurtig sortering Prøv det!

Valg af pivot:

Der er mange forskellige muligheder for at vælge pivoter.

Vælg altid det første element som en pivot .
Vælg altid det sidste element som en pivot (implementeret nedenfor)
Vælg et tilfældigt element som pivot .
Vælg midten som omdrejningspunkt.

Partitionsalgoritme:

Logikken er enkel, vi starter fra elementet længst til venstre og holder styr på indekset for mindre (eller lige store) elementer som jeg . Mens vi krydser, hvis vi finder et mindre element, bytter vi det aktuelle element med arr[i]. Ellers ignorerer vi det aktuelle element.

Lad os forstå hvordan partitionen og Quick Sort-algoritmen fungerer ved hjælp af følgende eksempel:

Overvej: arr[] = {10, 80, 30, 90, 40}.
analog kommunikation

Sammenlign 10 med pivoten, og da den er mindre end pivoten, arrangeres den i overensstemmelse med hinanden.

Partition i QuickSort: Sammenlign pivot med 10

Sammenlign 80 med pivoten. Det er større end pivot.

Partition i QuickSort: Sammenlign pivot med 80

Sammenlign 30 med pivot. Det er mindre end pivot, så arranger det i overensstemmelse hermed.

Partition i QuickSort: Sammenlign pivot med 30

Sammenlign 90 med pivoten. Den er større end pivoten.

Partition i QuickSort: Sammenlign pivot med 90

Anbring drejetappen i dens korrekte position.

Opdeling i QuickSort: Placer pivot i dens korrekte position

Illustration af Quicksort:

Da partitioneringsprocessen udføres rekursivt, bliver den ved med at placere pivoten i sin faktiske position i det sorterede array. Gentagne gange at sætte pivoter i deres faktiske position, sorteres arrayet.

Følg nedenstående billeder for at forstå, hvordan den rekursive implementering af partitionsalgoritmen hjælper med at sortere arrayet.

strenghåndtering i c++

Indledende partition på hovedarrayet:

Quicksort: Udførelse af partitionen

Opdeling af underarrays:

Quicksort: Udførelse af partitionen

Kodeimplementering af 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 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, der skal sorteres, // lav --> Startindeks, // høj --> Slutindeks statisk void quickSort(int[] arr, int lav, int høj) { if (lav< 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[] -->Array, der skal sorteres, // lav --> Startindeks, // høj --> Slutindeks statisk void quickSort(int[] arr, int lav, int høj) { if (lav< 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 funktion finder sted sidste element som pivot // Placer pivot som korrekt position // I Sorted Array, og placerer alle mindre til venstre // af pivot og alle større element til højre for pivotfunktionspartition(&$arr, $low,$high) { // Vælg pivotelementet $pivot= $arr[$high]; // Indeks af mindre element og indikerer // Den rigtige position af 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>

Produktion

Sorted Array 1 5 7 8 9 10>

Kompleksitetsanalyse af hurtig sortering :

Tidskompleksitet:

Bedste sag : Ω (N log (N))
Det bedste scenarie for quicksort opstår, når den pivot, der er valgt ved hvert trin, deler arrayet i nogenlunde lige store halvdele.
I dette tilfælde vil algoritmen lave afbalancerede partitioner, hvilket fører til effektiv sortering.
Gennemsnitlig tilfælde: θ ( N log (N))
Quicksorts gennemsnitlige sagsydelse er normalt meget god i praksis, hvilket gør den til en af de hurtigste sorteringsalgoritmer.
Værste tilfælde: O(N2)
Det værst tænkelige scenarie for Quicksort opstår, når pivoten ved hvert trin konsekvent resulterer i meget ubalancerede partitioner. Når arrayet allerede er sorteret, og pivoten altid er valgt som det mindste eller største element. For at afbøde det værst tænkelige scenarie bruges forskellige teknikker, såsom at vælge en god pivot (f.eks. median på tre) og bruge Randomized algoritme (Randomized Quicksort ) til at blande elementet før sortering.
Hjælpeplads: O(1), hvis vi ikke overvejer det rekursive stakrum. Hvis vi betragter det rekursive stack space så, i værste fald kunne quicksort gøre O ( N ).

Fordele ved hurtig sortering:

Det er en opdel-og-hersk-algoritme, der gør det nemmere at løse problemer.
Det er effektivt på store datasæt.
Den har en lav overhead, da den kun kræver en lille mængde hukommelse for at fungere.

Ulemper ved hurtig sortering:

Det har en worst-case tidskompleksitet på O(N²), som opstår, når pivot er valgt dårligt.
Det er ikke et godt valg til små datasæt.
Det er ikke en stabil sortering, hvilket betyder, at hvis to elementer har den samme nøgle, vil deres relative rækkefølge ikke blive bevaret i det sorterede output i tilfælde af hurtig sortering, for her bytter vi elementer i henhold til pivotens position (uden at overveje deres originale stillinger).

TechCodeview

QuickSort – Datastruktur og algoritmevejledning