Tri rapide

1. Algorithme de tri rapide
2. Exemple de tri rapide
3. Implémentation d’algorithme de tri rapide
4. Complexité de l’algorithme de tri rapide

Le tri rapide est un algorithme de tri très efficace basé sur le principe de l’algorithme de division et de conquête. Le tri rapide fonctionne en divisant le tableau en deux parties autour d’un élément pivot sélectionné. Il déplace les petits éléments vers le côté gauche du pivot et les grands éléments vers le côté droit. Ensuite, les sous-parties gauche et droite sont triées récursivement pour trier l’ensemble du tableau. Il est appelé tri rapide parce qu’il est environ 2 ou 3 fois plus rapide que les algorithmes de tri courants. Le tri rapide est largement utilisé pour la recherche d’informations et les calculs numériques à l’intérieur des structures de données.

Algorithme de tri rapide

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Prenons deux variables, beg & end, puis stockons l’index de l’élément de départ et de l’élément de fin.

Partition()

QuickSort()

Exemple de tri rapide

Supposons que nous ayons le tableau : (6,5,1,4,2,3). Nous allons le trier en utilisant l’algorithme de tri rapide.

Implémentation d’algorithme de tri rapide

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri rapide

Complexité temporelle

• Cas moyen

Le temps pris par le tri est donné par la relation de récurrence suivante :

 T(n) = T(k) + T(n-k-1) + θ(n)

k représente ici le nombre d’éléments plus petits/plus grands que l’élément pivot.

Le résultat de cette relation de récurrence donne T(n) = nLogn. Le cas moyen se produit lorsque nous obtenons des partitions aléatoires inégalement équilibrées. La complexité temporelle est de l’ordre de [Big Theta] : O(nLogn).

• Pire cas

T(n) = T(n-1) + θ(n)

Le pire cas se produit lorsque l’élément pivot est toujours soit le plus grand soit le plus petit élément du tableau. Dans ce cas, tous les éléments tombent dans un sous-tableau et des appels n doivent être effectués. Le pire cas de complexité temporelle est le [Big O] : O(n²).

• Meilleur cas

 T(n) = 2T(n/2) + θ(n)

Le meilleur cas se produit lorsque l’élément pivot sélectionné est toujours l’élément central ou lorsque les deux partitions sont équilibrées de manière égale, c’est-à-dire que la différence de taille est de 1 ou moins. Le meilleur cas de complexité temporelle est [Big Omega] : O(nLogn).

Complexité spatiale

La complexité spatiale moyenne de l’algorithme de tri rapide est de O(Logn). C’est l’espace requis par la pile de récursion. Mais dans le pire des cas, lorsque le tri d’un tableau nécessite la récursivité n, la complexité spatiale est O(n).