Tri rapide en Java

L'article suivant, Tri rapide en Java, fournit un aperçu de l'algorithme de tri rapide en Java. L'algorithme de tri rapide est l'un des algorithmes de tri efficaces et similaires à celui de l'algorithme de tri par fusion. Il s’agit de l’un des algorithmes les plus utilisés à des fins de tri en temps réel. La complexité temporelle dans le pire des cas de cet algorithme est O(n^2), la complexité temporelle moyenne est O(n log n) et la complexité temporelle dans le meilleur des cas est O(n log n).

La complexité spatiale si O(n log n), où n est la taille de l'entrée. Le processus de tri implique le partitionnement des entrées, les itérations récursives et le marquage d'un élément central pour chaque récursion. Le type de tri dans cet algorithme implique une comparaison des éléments adjacents de manière itérative.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Comment fonctionne le tri rapide en Java ?

L'algorithme de tri rapide peut être implémenté en Java en formant un pseudo-code avec une séquence d'étapes conçues et suivies de manière efficace.

• Le principe principal de l'algorithme de tri rapide sur lequel il fonctionne est basé sur l'approche diviser pour régner et constitue également un algorithme de tri efficace.
• Le tableau d'entrée est divisé en sous-tableaux, et la division est basée sur l'élément pivot, qui est un élément central. Les sous-tableaux de chaque côté de l'élément pivot sont les principales zones où le tri s'effectue réellement.
• L'élément pivot central est la base pour diviser le tableau en deux partitions où la moitié gauche des éléments du tableau est inférieure à l'élément pivot et la moitié droite des éléments du tableau est supérieure à l'élément pivot.
• Avant de considérer l'élément pivot, il peut s'agir de n'importe qui parmi les éléments d'un tableau. Celui-ci est normalement considéré comme celui du milieu, ou comme premier, ou comme dernier pour faciliter la compréhension. L'élément pivot peut être un élément aléatoire parmi n'importe lequel des éléments du tableau.
• Dans notre exemple, le dernier élément d'un tableau est considéré comme un élément pivot, où le partitionnement des sous-tableaux commence à partir de l'extrémité droite du tableau.
• Enfin, l'élément pivot sera dans sa position triée réelle après la fin du processus de tri, où le processus principal de tri réside dans la logique de partition de l'algorithme de tri.
• L'efficacité de l'algorithme dépend de la taille des sous-tableaux et de la manière dont ils sont équilibrés. Plus les sous-tableaux sont déséquilibrés, plus la complexité temporelle sera grande, conduisant à la pire complexité des cas.
• La sélection aléatoire des éléments pivots donne dans de nombreux cas la meilleure complexité temporelle au lieu de choisir un index de début, de fin ou du milieu particulier comme élément pivot.

Exemples d'implémentation du tri rapide en Java

L'algorithme QuickSort a été implémenté à l'aide du langage de programmation Java comme ci-dessous, et le code de sortie a été affiché sous le code.

• Le code prend initialement l'entrée en utilisant la méthode quickSortAlgo() avec le tableau, l'index initial et l'index final, c'est-à-dire la longueur du tableau comme arguments.
• Après avoir appelé la méthode quickSortAlgo(), il vérifie si l'index initial est inférieur à l'index final puis appelle la méthode arrayPartition() pour obtenir la valeur de l'élément pivot.
• L'élément de partition contient la logique d'agencement des éléments plus petits et plus grands en fonction des valeurs des éléments autour de l'élément pivot.
• Après avoir obtenu l'index de l'élément pivot après l'exécution de la méthode de partition, la méthode quickSortAlgo() est appelée par elle-même de manière récursive jusqu'à ce que tous les sous-tableaux soient partitionnés et triés complètement.
• Dans la logique de partition, le dernier élément est affecté comme élément pivot et le premier élément est comparé à l'élément pivot, c'est-à-dire le dernier où les éléments sont échangés selon qu'ils sont plus petits ou plus grands.
• Ce processus de récursion se produit jusqu'à ce que tous les éléments d'un tableau soient partitionnés et triés, où le résultat final est un tableau trié combiné.
• Les éléments sont échangés à l'intérieur de l'itération de la boucle for uniquement dans le cas où l'élément est inférieur ou égal à l'élément pivot.
• Après avoir terminé le processus d'itération, le dernier élément est échangé, c'est-à-dire que la valeur de l'élément pivot est déplacée vers la gauche afin que les nouvelles partitions soient créées, et le même processus se répète sous forme de récursion, ce qui entraîne une série de opérations de tri sur différentes partitions possibles sous forme de formation de sous-tableaux à partir des éléments du tableau donnés.
• Le code ci-dessous peut être exécuté sur n'importe quel IDE, et le résultat peut être vérifié en modifiant la valeur du tableau dans main(). La méthode main est utilisée uniquement dans le but d’obtenir la sortie dans la console. Dans le cadre des normes de codage Java, la méthode principale peut être supprimée ci-dessous et un objet peut être créé, et les méthodes ci-dessous peuvent être appelées en les rendant non statiques.

Implémentation de code de l'algorithme de tri rapide en Java

Voici une implémentation de code :

Code :

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

Sortie :

Conclusion

L'algorithme de tri rapide est efficace mais peu stable par rapport aux autres techniques de tri. L’efficacité des algorithmes de tri rapide diminue dans le cas d’un plus grand nombre d’éléments répétés, ce qui constitue un inconvénient. La complexité de l'espace est optimisée dans cet algorithme de tri rapide.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!