logo

TechCodeview

QuickSort – Vadnice za strukturo podatkov in algoritme

QuickSort je algoritem za razvrščanje, ki temelji na Algoritem deli in vladaj ki izbere element kot vrtišče in razdeli dano matriko okoli izbranega vrtišča tako, da vrtišče postavi na pravilno mesto v razvrščeni matriki.

Kako deluje QuickSort?

Ključni proces v hitro razvrščanje je particija () . Cilj particij je postaviti vrtišče (kateri koli element je lahko izbran za vrtišče) na pravilno mesto v razvrščeni matriki in vse manjše elemente postaviti levo od vrtišča, vse večje elemente pa desno od vrtišča. .

Razdelitev se izvede rekurzivno na vsaki strani vrtišča, potem ko je vrtišče postavljeno v pravilen položaj in to končno razvrsti niz.



Kako deluje Quicksort

Kako deluje Quicksort

primerjava nizov v Javi
Priporočena praksa Hitro razvrščanje Poskusite!

Izbira vrtišča:

Obstaja veliko različnih možnosti za izbiranje pivotov.

  • Za vrtišče vedno izberite prvi element .
  • Za vrtišče vedno izberi zadnji element (implementirano spodaj)
  • Izberite naključni element kot vrtišče .
  • Izberite sredino kot vrtišče.

Algoritem za razdelitev:

Logika je preprosta, začnemo od skrajno levega elementa in sledimo indeksu manjših (ali enakih) elementov kot jaz . Če med prečkanjem najdemo manjši element, trenutni element zamenjamo z arr[i]. V nasprotnem primeru ignoriramo trenutni element.

Razumejmo delovanje particije in algoritma za hitro razvrščanje s pomočjo naslednjega primera:

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

  • Primerjajte 10 z vrtiščem in, ker je manjši od vrtišča, ga uredite ustrezno.

Particija v QuickSort: primerjajte vrtišče z 10

  • Primerjajte 80 z vrtiščem. Je večji od vrtišča.

Particija v QuickSort: primerjajte pivot z 80

spletni gonilnik
  • Primerjaj 30 z vrtiščem. Je manjši od vrtišča, zato ga ustrezno uredite.

Particija v QuickSort: primerjajte pivot s 30

  • Primerjajte 90 z vrtiščem. Večji je od vrtišča.

Particija v QuickSort: primerjajte pivot z 90

  • Postavite vrtišče v pravilen položaj.

Particija v QuickSort: postavite vrtišče na pravilen položaj

Ilustracija Quicksort:

Ker se postopek particije izvaja rekurzivno, še naprej postavlja vrtišče na njegov dejanski položaj v razvrščeni matriki. Ponavljajoče se vrtišča v njihov dejanski položaj naredijo matriko razvrščeno.

Sledite spodnjim slikam, da boste razumeli, kako rekurzivna izvedba particijskega algoritma pomaga razvrstiti matriko.

pete davidson državljanstvo
  • Začetna particija na glavnem polju:

Quicksort: Izvedba particije

  • Razdelitev podnizkov:

Quicksort: Izvedba particije

Implementacija kode hitrega razvrščanja:

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[] -->Matrika za razvrščanje, // nizko --> začetni indeks, // visoko --> končni indeks 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>
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[] -->Matrika za razvrščanje, // nizko --> začetni indeks, // visoko --> končni indeks 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 ?>// Ta funkcija postavi zadnji element kot vrtišče // Postavi vrtišče na pravilen položaj // v razvrščeni matriki in vse manjše postavi levo // od vrtišča in vse večje elemente desno od particije vrtilne funkcije (&$arr, $low,$high) { // Izberite vrtilni element $pivot= $arr[$high]; // Indeks manjšega elementa in označuje // desni položaj vrtišča $i=($low-1); za ($j=$low;$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>
Izhod 
Sorted Array 1 5 7 8 9 10>

Analiza kompleksnosti hitrega razvrščanja :

Časovna zapletenost:

  • Najboljši primer : Ω (N log (N))
    Najboljši primer za hitro razvrščanje se zgodi, ko vrtišče, izbrano v vsakem koraku, razdeli matriko na približno enake polovice.
    V tem primeru bo algoritem naredil uravnotežene particije, kar vodi do učinkovitega razvrščanja.
  • Povprečni primer: θ (N log (N))
    Učinkovitost QuickSorta v povprečnih primerih je v praksi običajno zelo dobra, zaradi česar je eden najhitrejših algoritmov za razvrščanje.
  • Najslabši primer: O(N2)
    Najslabši možni scenarij za hitro razvrščanje se pojavi, ko vrtenje pri vsakem koraku dosledno povzroči zelo neuravnotežene particije. Ko je matrika že razvrščena in je vrtišče vedno izbrano kot najmanjši ali največji element. Za ublažitev najslabšega možnega scenarija se uporabljajo različne tehnike, kot je izbira dobrega vrtišča (npr. mediana tri) in uporaba naključnega algoritma (naključno hitro razvrščanje) za premeščanje elementa pred razvrščanjem.
  • Pomožni prostor: O(1), če ne upoštevamo rekurzivnega skladovnega prostora. Če upoštevamo prostor rekurzivnega sklada, bi lahko v najslabšem primeru prišlo do hitrega razvrščanja O ( n ).

Prednosti hitrega razvrščanja:

  • Je algoritem deli in vladaj, ki olajša reševanje problemov.
  • Učinkovit je pri velikih nizih podatkov.
  • Ima nizke stroške, saj za delovanje potrebuje le majhno količino pomnilnika.

Slabosti hitrega razvrščanja:

  • V najslabšem primeru ima časovno kompleksnost O(N2), ki se pojavi, ko je pivot izbran slabo.
  • To ni dobra izbira za majhne nize podatkov.
  • To ni stabilno razvrščanje, kar pomeni, da če imata dva elementa isti ključ, njun relativni vrstni red ne bo ohranjen v razvrščenem izhodu v primeru hitrega razvrščanja, ker tukaj zamenjujemo elemente glede na položaj vrtišča (brez upoštevanja njihovega izvirnika položaji).