Implémentation de l'algorithme Quicksort en Java

1. Vue d'ensemble

Dans ce didacticiel, nous explorerons en détail l'algorithme QuickSort, en nous concentrant sur son implémentation Java.

Nous discuterons également de ses avantages et inconvénients, puis analyserons sa complexité temporelle.

2. Algorithme QuickSort

Quicksort est un algorithme de tri qui s'appuie sur le principe de division et de conquête. Il a une complexité moyenne O (n log n) et c'est l'un des algorithmes de tri les plus utilisés, en particulier pour les gros volumes de données.

Il est important de se rappeler que Quicksort n'est pas un algorithme stable. Un algorithme de tri stable est un algorithme dans lequel les éléments avec les mêmes valeurs apparaissent dans le même ordre dans la sortie triée qu'ils apparaissent dans la liste d'entrée.

La liste d'entrée est divisée en deux sous-listes par un élément appelé pivot; une sous-liste avec des éléments inférieurs au pivot et une autre avec des éléments supérieurs au pivot. Ce processus se répète pour chaque sous-liste.

Enfin, toutes les sous-listes triées fusionnent pour former la sortie finale.

2.1. Étapes de l'algorithme

  1. Nous choisissons un élément de la liste, appelé le pivot. Nous l'utiliserons pour diviser la liste en deux sous-listes.
  2. Nous réorganisons tous les éléments autour du pivot - ceux qui ont la plus petite valeur sont placés devant lui, et tous les éléments plus grands que le pivot après lui. Après cette étape, le pivot est dans sa position finale. C'est l'étape importante de la partition.
  3. Nous appliquons les étapes ci-dessus de manière récursive aux deux sous-listes à gauche et à droite du pivot.

Comme nous pouvons le voir, le tri rapide est naturellement un algorithme récursif, comme toute approche de division et de conquête.

Prenons un exemple simple afin de mieux comprendre cet algorithme.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Supposons que nous choisissions 5 comme pivot de la simplicité
  2. Nous allons d'abord mettre tous les éléments inférieurs à 5 dans la première position du tableau: {3, 4, 5, 6, 5, 9}
  3. Nous le répéterons ensuite pour le sous-tableau de gauche {3,4}, en prenant 3 comme pivot
  4. Il n'y a pas d'éléments moins de 3
  5. On applique le tri rapide sur le sous-tableau à droite du pivot, c'est-à-dire {4}
  6. Ce sous-tableau se compose d'un seul élément trié
  7. Nous continuons avec la partie droite du tableau d'origine, {6, 5, 9} jusqu'à ce que nous obtenions le tableau ordonné final

2.2. Choisir le pivot optimal

Le point crucial dans QuickSort est de choisir le meilleur pivot. L'élément du milieu est, bien sûr, le meilleur, car il diviserait la liste en deux sous-listes égales.

Mais trouver l'élément du milieu à partir d'une liste non ordonnée est difficile et prend du temps, c'est pourquoi nous prenons comme pivot le premier élément, le dernier élément, la médiane ou tout autre élément aléatoire.

3. Implémentation en Java

La première méthode est quickSort () qui prend comme paramètres le tableau à trier, le premier et le dernier index. Tout d'abord, nous vérifions les indices et ne continuons que s'il reste des éléments à trier.

Nous obtenons l'index du pivot trié et l'utilisons pour appeler récursivement la méthode partition () avec les mêmes paramètres que la méthode quickSort () , mais avec des indices différents:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Continuons avec la méthode partition () . Par souci de simplicité, cette fonction prend le dernier élément comme pivot. Ensuite, vérifie chaque élément et le permute avant le pivot si sa valeur est plus petite.

À la fin du cloisonnement, tous les éléments inférieurs au pivot sont à gauche de celui-ci et tous les éléments supérieurs au pivot sont à droite de celui-ci. Le pivot est à sa position finale triée et la fonction renvoie cette position:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Analyse des algorithmes

4.1. Complexité temporelle

Dans le meilleur des cas, l'algorithme divisera la liste en deux sous-listes de taille égale. Ainsi, la première itération de la liste complète de taille n nécessite O (n) . Le tri des deux sous-listes restantes avec n / 2 éléments prend 2 * O (n / 2) chacun. En conséquence, l'algorithme QuickSort a la complexité de O (n log n) .

Dans le pire des cas, l'algorithme ne sélectionnera qu'un seul élément à chaque itération, donc O (n) + O (n-1) +… + O (1) , qui est égal à O (n2) .

En moyenne, QuickSort a une complexité O (n log n) , ce qui le rend adapté aux gros volumes de données.

4.2. QuickSort vs MergeSort

Voyons dans quels cas nous devrions choisir QuickSort sur MergeSort.

Bien que Quicksort et Mergesort aient une complexité temporelle moyenne de O (n log n) , Quicksort est l'algorithme préféré, car il a une complexité d'espace O (log (n)) . Mergesort, en revanche, nécessite un stockage supplémentaire O (n) , ce qui le rend assez coûteux pour les baies.

Quicksort nécessite d'accéder à différents index pour ses opérations, mais cet accès n'est pas directement possible dans les listes chaînées, car il n'y a pas de blocs continus; donc pour accéder à un élément, nous devons parcourir chaque nœud depuis le début de la liste chaînée. De plus, Mergesort est implémenté sans espace supplémentaire pour les LinkedLists.

Dans ce cas, les augmentations de frais généraux pour Quicksort et Mergesort sont généralement préférées.

5. Conclusion

Quicksort est un algorithme de tri élégant qui est très utile dans la plupart des cas.

C'est généralement un algorithme «en place», avec la complexité temporelle moyenne de O (n log n).

Un autre point intéressant à mentionner est que la méthode Java Arrays.sort () utilise Quicksort pour trier les tableaux de primitives. L'implémentation utilise deux pivots et fonctionne bien mieux que notre solution simple, c'est pourquoi pour le code de production, il est généralement préférable d'utiliser des méthodes de bibliothèque.

Comme toujours, le code pour l'implémentation de cet algorithme se trouve sur notre référentiel GitHub.