logo

TechCodeview

QuickSort – Tutoriale privind structura datelor și algoritmi

Sortare rapida este un algoritm de sortare bazat pe Algoritmul Divide and Conquer care alege un element ca pivot și parțiază matricea dată în jurul pivotului ales prin plasarea pivotului în poziția sa corectă în matricea sortată.

Cum funcționează QuickSort?

Procesul cheie în sortare rapida este o partiție () . Ținta partițiilor este de a plasa pivotul (orice element poate fi ales ca pivot) în poziția sa corectă în matricea sortată și de a pune toate elementele mai mici la stânga pivotului și toate elementele mai mari la dreapta pivotului .

Partiția se face recursiv pe fiecare parte a pivotului după ce pivotul este plasat în poziția sa corectă și aceasta sortează în cele din urmă matricea.



Cum funcționează Quicksort

Cum funcționează Quicksort

care este dimensiunea ecranului monitorului meu
Practică recomandată Sortare rapidă Încercați!

Alegerea pivotului:

Există multe opțiuni diferite pentru alegerea pivoților.

  • Alegeți întotdeauna primul element ca pivot .
  • Alegeți întotdeauna ultimul element ca pivot (implementat mai jos)
  • Alegeți un element aleatoriu ca pivot .
  • Alegeți mijlocul ca pivot.

Algoritm de partiție:

Logica este simplă, pornim de la elementul din stânga și urmărim indicele elementelor mai mici (sau egale) ca i . În timpul traversării, dacă găsim un element mai mic, schimbăm elementul curent cu arr[i]. În caz contrar, ignorăm elementul curent.

Să înțelegem funcționarea partiției și algoritmul de sortare rapidă cu ajutorul următorului exemplu:

Luați în considerare: arr[] = {10, 80, 30, 90, 40}.

  • Comparați 10 cu pivotul și, deoarece este mai mic decât pivotul, aranjați-l în mod corespunzător.

Partiție în QuickSort: comparați pivotul cu 10

  • Comparați 80 cu pivotul. Este mai mare decât pivotul.

Partiție în QuickSort: comparați pivotul cu 80

redenumiți în directorul linux
  • Comparați 30 cu pivot. Este mai puțin decât pivot, așa că aranjați-l în consecință.

Partiție în QuickSort: comparați pivotul cu 30

  • Comparați 90 cu pivotul. Este mai mare decât pivotul.

Partiție în QuickSort: comparați pivotul cu 90

  • Aranjați pivotul în poziția sa corectă.

Partiție în QuickSort: Plasați pivotul în poziția corectă

Ilustrație Quicksort:

Pe măsură ce procesul de partiție se face recursiv, acesta continuă să pună pivotul în poziția sa reală în matricea sortată. Punerea în mod repetat a pivoților în poziția lor reală face ca matricea să fie sortată.

Urmați imaginile de mai jos pentru a înțelege cum implementarea recursivă a algoritmului de partiție ajută la sortarea matricei.

dijkstra
  • Partiția inițială pe matricea principală:

Quicksort: Efectuarea partiției

  • Compartimentarea sub-tarilor:

Quicksort: Efectuarea partiției

Implementarea codului pentru sortarea rapidă:

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[] -->Matrice de sortat, // low --> Starting index, // high --> Ending index 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>
Piton 
# 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[] -->Matrice de sortat, // low --> Starting index, // high --> Ending index 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 ?>// Această funcție are loc ultimul element ca pivot // Plasează pivotul ca poziție corectă // În Sorted Array și plasează toate elementele mai mici la stânga // ale pivotului și toate elementele mai mari la dreapta partiției funcției pivot (&$arr, $low,$high) { // Alegeți elementul Pivot $pivot= $arr[$high]; // Indexul elementului mai mic și indică // Poziția dreaptă a pivotului $i=($low-1); pentru($j=$scăzut;$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>
Ieșire 
Sorted Array 1 5 7 8 9 10>

Analiza complexității sortării rapide :

Complexitatea timpului:

  • Cel mai bun caz : Ω (N log (N))
    Cel mai bun scenariu pentru sortarea rapidă apare atunci când pivotul ales la fiecare pas împarte matricea în jumătăți aproximativ egale.
    În acest caz, algoritmul va face partiții echilibrate, ceea ce duce la o sortare eficientă.
  • Caz mediu: θ ( N log (N))
    Performanța medie a cazului Quicksort este de obicei foarte bună în practică, ceea ce îl face unul dintre cele mai rapide algoritmi de sortare.
  • Cel mai rău caz: O(N2)
    Cel mai rău scenariu pentru Quicksort apare atunci când pivotul la fiecare pas are ca rezultat în mod constant partiții foarte dezechilibrate. Când matricea este deja sortată și pivotul este întotdeauna ales ca cel mai mic sau mai mare element. Pentru a atenua scenariul cel mai rău, sunt utilizate diverse tehnici, cum ar fi alegerea unui pivot bun (de exemplu, mediana de trei) și utilizarea algoritmului randomizat (Randomized Quicksort) pentru a amesteca elementul înainte de sortare.
  • Spațiu auxiliar: O(1), dacă nu luăm în considerare spațiul de stivă recursiv. Dacă luăm în considerare spațiul de stivă recursiv, atunci, în cel mai rău caz ar putea face sortarea rapidă O ( N ).

Avantajele sortării rapide:

  • Este un algoritm de împărțire și cucerire care facilitează rezolvarea problemelor.
  • Este eficient pe seturi mari de date.
  • Are o supraîncărcare redusă, deoarece necesită doar o cantitate mică de memorie pentru a funcționa.

Dezavantajele sortării rapide:

  • Are o complexitate de timp în cel mai rău caz de O(N2), care apare atunci când pivotul este ales prost.
  • Nu este o alegere bună pentru seturi mici de date.
  • Nu este o sortare stabilă, adică dacă două elemente au aceeași cheie, ordinea lor relativă nu va fi păstrată în ieșirea sortată în cazul sortării rapide, deoarece aici schimbăm elementele în funcție de poziția pivotului (fără a lua în considerare originalul lor). posturi).