Introduction au 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 qui est efficace et similaire à 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 dans le cas moyen est O (n log n) et la complexité temporelle dans le meilleur cas est O (n log n).

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

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.

  1. Le principe principal de l'algorithme de tri rapide qui fonctionne est basé sur l'approche diviser pour régner et est également un algorithme de tri efficace.
  2. 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 zones principales où le tri a lieu.
  3. 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.
  4. Avant de considérer l'élément pivot, il peut s'agir de n'importe qui parmi les éléments d'un tableau. Ceci est normalement considéré comme le milieu ou le premier ou le dernier pour la facilité de compréhension. L'élément pivot peut être un élément aléatoire de n'importe lequel des éléments du tableau.
  5. 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 à l'extrémité droite du tableau.
  6. Enfin, l'élément pivot sera dans sa position de tri réelle après l'achèvement du processus de tri, où le processus de tri principal réside dans la logique de partition de l'algorithme de tri.
  7. L'efficacité de l'algorithme dépend de la taille des sous-réseaux et de la façon dont ils sont équilibrés. Plus les sous-matrices sont déséquilibrées, plus la complexité temporelle conduira à la complexité du pire des cas.
  8. La sélection des éléments pivot de manière aléatoire entraîne la meilleure complexité temporelle dans de nombreux cas au lieu de choisir un index de début, de fin ou intermédiaire particulier comme éléments pivot.

Exemples pour implémenter le tri rapide en Java

L'algorithme QuickSort a été implémenté en utilisant le langage de programmation Java comme ci-dessous et le code de sortie a été affiché sous le code.

  1. 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.
  2. 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.
  3. L'élément de partition contient la logique de disposition des éléments plus petits et plus grands autour de l'élément pivot en fonction des valeurs des éléments.
  4. 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 d'elle-même récursivement jusqu'à ce que tous les sous-tableaux soient partitionnés et triés complètement.
  5. Dans la logique de partition, le dernier élément est affecté en tant qu'é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.
  6. Ce processus de récursivité 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é.
  7. Les éléments sont échangés à l'intérieur de l'itération for-loop uniquement dans le cas où l'élément est inférieur ou égal à l'élément pivot.
  8. 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 que le même processus se répète sous forme de récursivité, ce qui se traduit par une série d'opérations de tri sur différentes partitions possibles comme une formation de sous-tableaux à partir des éléments de tableau donnés.
  9. Le code ci-dessous peut être exécuté sur n'importe quel IDE et la sortie peut être vérifiée en modifiant la valeur du tableau dans le main () La méthode principale 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 d'algorithme de tri rapide en Java

/*
* 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);
)
)
)

Production:

Conclusion

L'algorithme de tri rapide est efficace mais pas très stable par rapport à d'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 est un inconvénient. La complexité de l'espace est optimisée dans cet algorithme de tri rapide.

Articles recommandés

Ceci est un guide de tri rapide en Java. Nous discutons ici du fonctionnement de Tri rapide en Java ainsi que d'un exemple et de l'implémentation du code. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus -

  1. Tri de tas en Java
  2. Qu'est-ce qu'un arbre binaire en Java?
  3. Manipulation de bits en Java
  4. Présentation du tri par fusion en JavaScript
  5. Présentation du tri rapide en JavaScript
  6. Tri de tas en Python
  7. Top 6 des algorithmes de tri en JavaScript

Catégorie:

Développement de logiciels