logo

TechCodeview

QuickSort – Didacticiels sur la structure des données et les algorithmes

Tri rapide est un algorithme de tri basé sur Algorithme Diviser pour Régner qui sélectionne un élément comme pivot et partitionne le tableau donné autour du pivot choisi en plaçant le pivot dans sa position correcte dans le tableau trié.

Comment fonctionne le tri rapide ?

Le processus clé dans tri rapide est un cloison() . Le but des partitions est de placer le pivot (n'importe quel élément peut être choisi comme pivot) à sa position correcte dans le tableau trié et de placer tous les éléments plus petits à gauche du pivot et tous les éléments plus grands à droite du pivot. .

La partition est effectuée de manière récursive de chaque côté du pivot une fois le pivot placé dans sa position correcte, ce qui trie finalement le tableau.



Comment fonctionne le tri rapide

Comment fonctionne le tri rapide

Linux changer le nom du répertoire
Pratique recommandée Tri rapide Essayez-le !

Choix du pivot :

Il existe de nombreux choix différents pour choisir les pivots.

  • Choisissez toujours le premier élément comme pivot .
  • Choisissez toujours le dernier élément comme pivot (implémenté ci-dessous)
  • Choisissez un élément aléatoire comme pivot .
  • Choisissez le milieu comme pivot.

Algorithme de partition :

La logique est simple, nous partons de l'élément le plus à gauche et gardons une trace de l'index des éléments plus petits (ou égaux) comme je . Lors du parcours, si nous trouvons un élément plus petit, nous échangeons l'élément courant avec arr[i]. Sinon, nous ignorons l'élément courant.

Comprenons le fonctionnement de la partition et l'algorithme de tri rapide à l'aide de l'exemple suivant :

Considérez : arr[] = {10, 80, 30, 90, 40}.

  • Comparez 10 avec le pivot et comme il est inférieur au pivot, disposez-le en conséquence.

Partition dans QuickSort : comparez le pivot avec 10

  • Comparez 80 avec le pivot. C’est plus grand que le pivot.

Partition dans QuickSort : comparez le pivot avec 80

balançoire java
  • Comparez 30 avec pivot. C'est moins qu'un pivot, alors organisez-le en conséquence.

Partition dans QuickSort : comparez le pivot avec 30

  • Comparez 90 avec le pivot. Il est supérieur au pivot.

Partition dans QuickSort : comparez le pivot avec 90

  • Disposez le pivot dans sa bonne position.

Partition dans QuickSort : placez le pivot dans sa position correcte

Illustration du tri rapide :

Comme le processus de partition est effectué de manière récursive, il continue de placer le pivot à sa position réelle dans le tableau trié. Placer à plusieurs reprises les pivots dans leur position réelle permet de trier le tableau.

Suivez les images ci-dessous pour comprendre comment l'implémentation récursive de l'algorithme de partition aide à trier le tableau.

algorithme de tri par fusion
  • Partition initiale sur la baie principale :

Tri rapide : exécution de la partition

  • Partitionnement des sous-tableaux :

Tri rapide : exécution de la partition

Implémentation du code du tri rapide :

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[] -->Tableau à trier, // faible --> Index de début, // élevé --> Index de fin 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[] -->Tableau à trier, // faible --> Index de début, // élevé --> Index de fin 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 ?>// Cette fonction prend place en dernier élément comme pivot // Place le pivot dans la position correcte // Dans un tableau trié, et place tous les plus petits à gauche // du pivot et tous les éléments plus grands à sa droite de la fonction pivot partition(&$arr, $low,$high) { // Choisissez l'élément pivot $pivot= $arr[$high]; // Index d'un élément plus petit et indique // La bonne position du pivot $i=($low-1); pour($j=$faible;$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>
Sortir 
Sorted Array 1 5 7 8 9 10>

Analyse de complexité du tri rapide :

Complexité temporelle :

  • Meilleur cas : Ω (N log (N))
    Le meilleur scénario pour le tri rapide se produit lorsque le pivot choisi à chaque étape divise le tableau en moitiés à peu près égales.
    Dans ce cas, l’algorithme réalisera des partitions équilibrées, conduisant à un tri efficace.
  • Cas moyen : θ ( N log (N))
    Les performances moyennes de Quicksort sont généralement très bonnes dans la pratique, ce qui en fait l’un des algorithmes de tri les plus rapides.
  • Pire des cas : O(N2)
    Le pire des cas pour le tri rapide se produit lorsque le pivot à chaque étape entraîne systématiquement des partitions très déséquilibrées. Lorsque le tableau est déjà trié et que le pivot est toujours choisi comme élément le plus petit ou le plus grand. Pour atténuer le pire des cas, diverses techniques sont utilisées, telles que le choix d'un bon pivot (par exemple, médiane de trois) et l'utilisation d'un algorithme aléatoire (Randomized Quicksort) pour mélanger l'élément avant le tri.
  • Espace auxiliaire : O(1), si l’on ne considère pas l’espace de pile récursif. Si nous considérons l'espace de pile récursif, dans le pire des cas, un tri rapide pourrait rendre Ô ( N ).

Avantages du tri rapide :

  • Il s’agit d’un algorithme diviser pour régner qui facilite la résolution des problèmes.
  • Il est efficace sur de grands ensembles de données.
  • Il a une faible surcharge, car il ne nécessite qu’une petite quantité de mémoire pour fonctionner.

Inconvénients du tri rapide :

  • Il a une complexité temporelle dans le pire des cas de O(N2), ce qui se produit lorsque le pivot est mal choisi.
  • Ce n'est pas un bon choix pour les petits ensembles de données.
  • Ce n'est pas un tri stable, ce qui signifie que si deux éléments ont la même clé, leur ordre relatif ne sera pas conservé dans la sortie triée en cas de tri rapide, car ici nous échangeons les éléments en fonction de la position du pivot (sans tenir compte de leur original postes).