Menu

QuickSort en Java - Algorithme, illustration et implémentation

  • Principal
  • Autre
  • QuickSort en Java - Algorithme, illustration et implémentation

quicksort java algorithm

Essayez Notre Instrument Pour Éliminer Les Problèmes

meilleur VPN pour le streaming

Ce didacticiel explique l'algorithme Quicksort en Java, ses illustrations, l'implémentation QuickSort en Java à l'aide d'exemples de code:

La technique de tri par tri rapide est largement utilisée dans les applications logicielles. Quicksort utilise une stratégie de division et de conquête telle que le tri par fusion.

Dans l'algorithme de tri rapide, un élément spécial appelé «pivot» est d'abord sélectionné et le tableau ou la liste en question est partitionné en deux sous-ensembles. Les sous-ensembles partitionnés peuvent être de taille égale ou non.

=> Lisez la série de formations Easy Java.

Technique QuickSort en Java

Les cloisons sont telles que tous les éléments inférieurs à l'élément de pivot sont vers la gauche du pivot et les éléments supérieurs au pivot se trouvent à droite du pivot. La routine Quicksort trie de manière récursive les deux sous-listes. Quicksort fonctionne de manière efficace et plus rapide, même pour des tableaux ou des listes plus volumineux.

Ce que vous apprendrez:

Partition de tri rapide Java

Le partitionnement est le processus clé de la technique Quicksort. Alors, qu'est-ce que le partitionnement?

Étant donné un tableau A, on choisit une valeur x appelée pivot telle que tous les éléments inférieurs à x sont avant x, et tous les éléments supérieurs à x sont après x.

Une valeur pivot peut être l'une des suivantes:

  • Le premier élément du tableau
  • Le dernier élément du tableau
  • L'élément central du tableau
  • Tout élément aléatoire du tableau

Cette valeur pivot est ensuite placée à sa bonne position dans le tableau en partitionnant le tableau. Ainsi, le résultat du processus de «partitionnement» est la valeur de pivot à sa position correcte et les éléments moins que pivotent à gauche et les éléments plus grands qu’un pivot à droite.

Considérez le diagramme suivant qui explique le processus de partitionnement.

processus de partitionnement

Le diagramme ci-dessus montre le processus de partitionnement du tableau en sélectionnant à plusieurs reprises le dernier élément du tableau en tant que pivot. À chaque niveau, notez que nous partitionnons le tableau en deux sous-tableaux en plaçant le pivot à sa position correcte.

Ensuite, nous listons l'algorithme et le pseudo-code pour la technique de tri rapide qui inclut également la routine de partition.

Algorithme de tri rapide Java

L'algorithme général de tri rapide est donné ci-dessous.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Vous trouverez ci-dessous le pseudo-code de la technique de tri rapide.

Pseudocode pour un tri rapide

Voici le pseudo-code pour une technique de tri rapide. Notez que nous avons fourni le pseudo-code pour la routine de tri rapide et de partitionnement.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

Illustration

Voyons l’illustration de l’algorithme de tri rapide. Prenons l'exemple du tableau suivant. Ici, nous avons sélectionné le dernier élément comme pivot.

Comme indiqué, le premier élément est étiqueté bas et le dernier élément est élevé.

Illustration de l

Comme le montre l'illustration ci-dessus, il existe deux pointeurs, haut et bas, qui pointent respectivement vers le dernier et le premier élément du tableau. Ces deux pointeurs sont déplacés à mesure que le tri rapide progresse.

Lorsque l'élément pointé par le pointeur bas devient plus grand que l'élément pivot et que l'élément pointé par le pointeur haut est inférieur à l'élément pivot, nous échangeons les éléments pointés par le pointeur bas et haut, et chaque pointeur avance d'une position.

Les étapes ci-dessus sont effectuées jusqu'à ce que les deux pointeurs se croisent dans le tableau. Une fois qu'ils se croisent, l'élément pivot prend sa bonne position dans le tableau. À ce stade, le tableau est partitionné et maintenant nous pouvons trier chaque sous-tableau indépendamment en appliquant récursivement un algorithme de tri rapide à chacun des sous-tableaux.

Implémentation Quicksort en Java

La technique QuickSort peut être implémentée en Java à l'aide de la récursivité ou de l'itération. Dans cette section, nous verrons ces deux techniques.

Quicksort récursif

Nous savons que la technique de base du tri rapide illustrée ci-dessus utilise la récursivité pour trier le tableau. Dans le tri rapide récursif après partitionnement du tableau, la routine de tri rapide est appelée de manière récursive pour trier les sous-tableaux.

L'implémentation ci-dessous illustre la technique de tri rapide utilisant la récursivité.

comment ouvrir 7z sur mac
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Production:

Baie d’origine: (4, -1, 6, 8, 0, 5, -3)
Tableau trié: (-3, -1, 0, 4, 5, 6, 8)

Quicksort récursif - sortie

Tri rapide itératif

Dans le tri rapide itératif, nous utilisons la pile auxiliaire pour placer des paramètres intermédiaires au lieu d'utiliser la récursivité et trier les partitions.

Le programme Java suivant implémente un tri rapide itératif.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Production:

Baie d’origine: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Tableau trié: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Tri rapide itératif - sortie

Questions fréquemment posées

Q # 1) Comment fonctionne un tri rapide?

Répondre: Quicksort utilise une stratégie de division et de conquête. Quicksort partitionne d'abord un tableau autour d'un élément pivot sélectionné et génère des sous-tableaux qui sont triés de manière récursive.

Q # 2) Quelle est la complexité temporelle de Quicksort?

où regarder des anime gratuits en ligne

Répondre: La complexité temporelle du tri rapide sur une moyenne est O (nlogn). Dans le pire des cas, c'est O (n ^ 2) identique au tri de sélection.

Q # 3) Où est utilisé Quicksort?

Répondre: Quicksort est principalement utilisé dans les applications récursives. Quicksort fait partie de C-library. En outre, presque les langages de programmation qui utilisent le tri intégré implémentent un tri rapide.

Q # 4) Quel est l'avantage de Quicksort?

Répondre:

  • Quicksort est un algorithme efficace et peut facilement trier même une énorme liste d'éléments.
  • Il s'agit d'un tri sur place et n'a donc pas besoin d'espace ou de mémoire supplémentaire.
  • Il est largement utilisé et constitue un moyen efficace de trier des ensembles de données de toute longueur.

Q # 5) Pourquoi Quicksort est-il meilleur que le tri par fusion?

Répondre: La principale raison pour laquelle le tri rapide est meilleur que le tri par fusion est que le tri rapide est une méthode de tri sur place et ne nécessite pas d'espace mémoire supplémentaire. Le tri par fusion nécessite de la mémoire supplémentaire pour le tri intermédiaire.

Conclusion

Quicksort est considéré comme le meilleur algorithme de tri, principalement en raison de son efficacité à trier même un énorme ensemble de données en temps O (nlogn).

Quicksort est également un tri sur place et ne nécessite pas d'espace mémoire supplémentaire. Dans ce tutoriel, nous avons vu l'implémentation récursive et itérative de quicksort.

Dans notre prochain tutoriel, nous continuerons avec les méthodes de tri en Java.

=> Jetez un œil au guide du débutant Java ici.

lecture recommandée

^