logo

TechCodeview

QuickSort — datu struktūras un algoritmu apmācības

QuickSort ir šķirošanas algoritms, kura pamatā ir Dali un iekaro algoritms kas izvēlas elementu kā šarnīra punktu un sadala doto masīvu ap izvēlēto šarnīra punktu, novietojot rakursu pareizajā pozīcijā sakārtotajā masīvā.

Kā darbojas QuickSort?

Galvenais process iekšā ātrā šķirošana ir nodalījums () . Sadalījumu mērķis ir novietot rakursu (jebkuru elementu var izvēlēties par pivot) tā pareizajā pozīcijā sakārtotajā masīvā un visus mazākos elementus novietot pa kreisi no rakursa, un visus lielākos elementus pa labi no rakursa. .

Sadalīšana tiek veikta rekursīvi katrā šarnīra pusē pēc tam, kad šarnīrs ir novietots pareizajā pozīcijā, un tas beidzot sakārto masīvu.



Kā darbojas Quicksort

Kā darbojas Quicksort

atgriežot masīvu java
Ieteicamā prakse Ātrā šķirošana Izmēģiniet to!

Rakursa izvēle:

Ir daudzas dažādas šarnīra izvēles iespējas.

  • Vienmēr izvēlieties pirmo elementu kā pagrieziena punktu .
  • Vienmēr izvēlieties pēdējo elementu kā rakursu (ieviests tālāk)
  • Izvēlieties izlases elementu kā rakursu .
  • Izvēlieties vidu kā šarnīrsavienojumu.

Sadalīšanas algoritms:

Loģika ir vienkārša, mēs sākam no vistālāk kreisā elementa un sekojam mazāku (vai vienādu) elementu indeksam kā i . Braucot, ja atrodam mazāku elementu, pašreizējo elementu apmainām ar arr[i]. Pretējā gadījumā mēs ignorējam pašreizējo elementu.

Ļaujiet mums saprast nodalījuma darbību un ātrās kārtošanas algoritmu, izmantojot šādu piemēru:

pārvērst par virkni

Apsveriet: arr[] = {10, 80, 30, 90, 40}.

  • Salīdziniet 10 ar šarnīrsavienojumu un, tā kā tas ir mazāks nekā šarnīrs, sakārtojiet to atbilstoši.

Sadalījums programmā QuickSort: salīdziniet pivot ar 10

  • Salīdziniet 80 ar šarnīrsavienojumu. Tas ir lielāks nekā šarnīrs.

Sadalījums programmā QuickSort: salīdziniet pivot ar 80

  • Salīdziniet 30 ar šarnīrsavienojumu. Tas ir mazāks par pagriezienu, tāpēc sakārtojiet to atbilstoši.

Sadalījums programmā QuickSort: salīdziniet pivot ar 30

  • Salīdziniet 90 ar šarnīrsavienojumu. Tas ir lielāks nekā šarnīrs.

Sadalījums programmā QuickSort: salīdziniet pivot ar 90

  • Novietojiet šarnīrsavienojumu pareizajā pozīcijā.

Sadalījums QuickSort: novietojiet šarnīrsavienojumu pareizajā pozīcijā

Quicksort ilustrācija:

Tā kā sadalīšanas process tiek veikts rekursīvi, tas turpina novietot pagrieziena punktu tā faktiskajā pozīcijā sakārtotajā masīvā. Atkārtoti ievietojot pagriezienus to faktiskajā pozīcijā, masīvs tiek sakārtots.

Izpildiet tālāk redzamos attēlus, lai saprastu, kā nodalījuma algoritma rekursīvā ieviešana palīdz kārtot masīvu.

Pīta Deividsona pilsonība
  • Sākotnējais nodalījums galvenajā masīvā:

Ātrā kārtošana: veic nodalījumu

  • Apakšbloku sadalīšana:

Ātrā kārtošana: veic nodalījumu

Ātrās kārtošanas koda ieviešana:

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[] -->Kārtojamais masīvs, // zems --> sākuma indekss, // augsts --> beigu indekss static void quickSort(int[] arr, int zems, int augsts) { if (zems< 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[] -->Kārtojamais masīvs, // zems --> sākuma indekss, // augsts --> beigu indekss static void quickSort(int[] arr, int zems, int augsts) { if (zems< 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 ?>// Šī funkcija veic pēdējo elementu kā pivot // Novietojiet pivot kā pareizo pozīciju // Sakārtotajā masīvā un novieto visus mazākus uz kreiso // no rakurstacijas un visus lielākos elementus pa labi no pagrieziena funkcijas nodalījuma (&$arr, $low,$high) { // Izvēlieties rakursta elementu $pivot= $arr[$high]; // Mazāka elementa indekss un norāda // Pareizo šarnīra pozīciju $i=($low-1); for($j=$mazs;$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>
Izvade 
Sorted Array 1 5 7 8 9 10>

Ātrās šķirošanas sarežģītības analīze :

Laika sarežģītība:

  • Labākais gadījums : Ω (N log (N))
    Labākais ātrās kārtošanas scenārijs notiek, kad katrā solī izvēlētais šarnīrs sadala masīvu aptuveni vienādās daļās.
    Šajā gadījumā algoritms izveidos līdzsvarotus nodalījumus, kas novedīs pie efektīvas kārtošanas.
  • Vidējais gadījums: θ ( N log (N))
    Quicksort vidējā veiktspēja praksē parasti ir ļoti laba, padarot to par vienu no ātrākajiem šķirošanas algoritmiem.
  • Sliktākais gadījums: O(N2)
    Sliktākais ātrās kārtošanas scenārijs rodas, ja pagrieziens katrā solī konsekventi rada ļoti nelīdzsvarotus nodalījumus. Kad masīvs jau ir sakārtots un šarnīrs vienmēr tiek izvēlēts kā mazākais vai lielākais elements. Lai mazinātu sliktākā gadījuma scenāriju, tiek izmantoti dažādi paņēmieni, piemēram, laba pagrieziena izvēle (piem., mediāna no trīs) un nejauša algoritma izmantošana (Randomizēta ātrā kārtošana), lai pirms kārtošanas sajauktu elementu.
  • Palīgtelpa: O(1), ja neņemam vērā rekursīvo steka telpu. Ja mēs ņemam vērā rekursīvo steka vietu, tad sliktākajā gadījumā varētu izveidot ātru šķirošanu O ( N ).

Ātrās šķirošanas priekšrocības:

  • Tas ir “skaldi un valdi” algoritms, kas atvieglo problēmu risināšanu.
  • Tas ir efektīvs lielām datu kopām.
  • Tam ir zemas pieskaitāmās izmaksas, jo tā darbībai ir nepieciešams tikai neliels atmiņas apjoms.

Ātrās šķirošanas trūkumi:

  • Tam ir sliktākā gadījuma laika sarežģītība O(N2), kas rodas, ja šarnīrs ir izvēlēts slikti.
  • Tā nav laba izvēle nelielām datu kopām.
  • Tā nav stabila kārtošana, kas nozīmē, ka, ja diviem elementiem ir viena un tā pati atslēga, to relatīvā secība ātrās kārtošanas gadījumā netiks saglabāta sakārtotajā izvadā, jo šeit mēs apmainām elementus atbilstoši pivota pozīcijai (neņemot vērā to sākotnējo pozīcijas).