logo

TechCodeview

QuickSort - Tutorials d'estructura de dades i algorisme

QuickSort és un algorisme d'ordenació basat en Algorisme Divide and Conquer que tria un element com a pivot i divideix la matriu donada al voltant del pivot escollit col·locant el pivot a la seva posició correcta a la matriu ordenada.

Com funciona QuickSort?

El procés clau en quickSort és un partició () . L'objectiu de les particions és col·locar el pivot (qualsevol element es pot triar com a pivot) a la seva posició correcta a la matriu ordenada i posar tots els elements més petits a l'esquerra del pivot i tots els elements més grans a la dreta del pivot. .

La partició es fa de forma recursiva a cada costat del pivot després de col·locar el pivot a la seva posició correcta i això finalment ordena la matriu.



Com funciona Quicksort

Com funciona Quicksort

fer mentre estàs en java
Pràctica recomanada Ordenació ràpida Prova-ho!

Elecció del pivot:

Hi ha moltes opcions diferents per triar pivots.

  • Trieu sempre el primer element com a pivot .
  • Trieu sempre l'últim element com a pivot (implementat a continuació)
  • Trieu un element aleatori com a pivot .
  • Trieu el centre com a pivot.

Algoritme de partició:

La lògica és senzilla, partim de l'element més esquerre i fem un seguiment de l'índex d'elements més petits (o iguals) com i . Mentre es recorre, si trobem un element més petit, intercanviem l'element actual amb arr[i]. En cas contrari, ignorarem l'element actual.

Entenem el funcionament de la partició i l'algorisme Quick Sort amb l'ajuda de l'exemple següent:

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

  • Compareu el 10 amb el pivot i com que és inferior al pivot, disposeu-lo de manera transversal.

Partició a QuickSort: compareu el pivot amb 10

  • Compara 80 amb el pivot. És més gran que el pivot.

Partició a QuickSort: compareu el pivot amb 80

ml a oz
  • Compara 30 amb pivot. És menys que pivot, així que organitzeu-lo en conseqüència.

Partició a QuickSort: compareu el pivot amb 30

  • Compara 90 amb el pivot. És més gran que el pivot.

Partició a QuickSort: compareu el pivot amb 90

  • Col·loqueu el pivot en la seva posició correcta.

Partició a QuickSort: col·loqueu el pivot a la seva posició correcta

Il·lustració de Quicksort:

Com que el procés de partició es fa de forma recursiva, continua posant el pivot a la seva posició real a la matriu ordenada. Posar els pivots repetidament a la seva posició real fa que la matriu estigui ordenada.

Seguiu les imatges següents per entendre com la implementació recursiva de l'algoritme de partició ajuda a ordenar la matriu.

java priorityqueue
  • Partició inicial a la matriu principal:

Quicksort: realitzant la partició

  • Partició dels subbarrays:

Quicksort: realitzant la partició

Implementació de codi de 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 
// 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[] -->Matriu a ordenar, // baix --> Índex inicial, // alt --> Índex final 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[] -->Matriu a ordenar, // baix --> Índex inicial, // alt --> Índex final 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 ?>// Aquesta funció té lloc l'últim element com a pivot // Col·loca el pivot com a posició correcta // A Sorted Array, i col·loca tots els més petits a l'esquerra // del pivot i els més grans a la dreta de la partició de la funció de pivot (&$arr, $baix,$alt) { // Trieu l'element de pivot $pivot= $arr[$alt]; // Índex de l'element més petit i indica // La posició correcta del pivot $i=($low-1); per($j=$baix;$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>
Sortida 
Sorted Array 1 5 7 8 9 10>

Anàlisi de complexitat de Quick Sort :

Complexitat temporal:

  • Millor cas : Ω (N log (N))
    El millor dels casos per a la classificació ràpida es produeix quan el pivot escollit a cada pas divideix la matriu en meitats aproximadament iguals.
    En aquest cas, l'algoritme farà particions equilibrades, donant lloc a una ordenació eficient.
  • Cas mitjà: θ ( N log (N))
    El rendiment mitjà de Quicksort sol ser molt bo a la pràctica, cosa que el converteix en un dels algorismes d'ordenació més ràpids.
  • El pitjor dels casos: O(N2)
    El pitjor dels casos per a Quicksort es produeix quan el pivot a cada pas dóna lloc de manera constant a particions molt desequilibrades. Quan la matriu ja està ordenada i el pivot sempre s'escull com l'element més petit o més gran. Per mitigar l'escenari del pitjor dels casos, s'utilitzen diverses tècniques, com ara triar un bon pivot (per exemple, una mitjana de tres) i utilitzar un algorisme aleatori (Randomized Quicksort) per barrejar l'element abans d'ordenar.
  • Espai auxiliar: O(1), si no tenim en compte l'espai recursiu de la pila. Si considerem l'espai recursiu de la pila, en el pitjor dels casos, podria fer-se una classificació ràpida O ( N ).

Avantatges de Quick Sort:

  • És un algorisme de divideix i venços que facilita la resolució de problemes.
  • És eficient en grans conjunts de dades.
  • Té una sobrecàrrega baixa, ja que només requereix una petita quantitat de memòria per funcionar.

Desavantatges de Quick Sort:

  • Té una complexitat temporal en el pitjor dels casos de O(N2), que es produeix quan el pivot es tria malament.
  • No és una bona opció per a conjunts de dades petits.
  • No és una ordenació estable, és a dir, si dos elements tenen la mateixa clau, el seu ordre relatiu no es conservarà a la sortida ordenada en cas d'ordenació ràpida, perquè aquí estem intercanviant elements segons la posició del pivot (sense considerar el seu original). posicions).