Tri rapide en Java expliqué

Convention de réduction de moitié

Lorsque le nombre d'éléments d'une liste est pair, diviser par deux la liste signifie que la première moitié littérale de la liste est la première moitié et la seconde moitié littérale de la liste est la seconde moitié. L'élément milieu (milieu) de toute la liste est le dernier élément de la première liste. Cela signifie que l'index du milieu est de longueur / 2 – 1, car le comptage d'index commence à partir de zéro. La longueur est le nombre d'éléments dans la liste. Par exemple, si le nombre d'éléments est de 8, alors la première moitié de la liste a 4 éléments et la seconde moitié de la liste a également 4 éléments. C'est bon. Étant donné que le comptage d'index commence à partir de 0, l'index du milieu est 3 = 8 / 2 - 1.

Qu'en est-il du cas, lorsque le nombre d'éléments dans la liste ou la sous-liste est impair ? Au départ, la longueur est toujours divisée par 2. Par convention, le nombre d'éléments dans la première moitié de cette division est de longueur / 2 + 1/2. Le comptage d'index commence à partir de zéro. L'indice du milieu est donné par la longueur / 2 – 1/2. Ceci est considéré comme le moyen terme, par convention. Par exemple, si le nombre d'éléments dans une liste est de 5, alors l'index du milieu est 2 = 5/2 – 1/2. Et, il y a trois éléments dans la première moitié de la liste et deux éléments dans la seconde moitié. L'élément du milieu de toute la liste est le troisième élément à l'index, 2, qui est l'index du milieu car le comptage d'index commence à partir de 0.

La division de cette manière est un exemple d'arithmétique entière.

Médiane de trois valeurs

Question : Quelle est la médiane de la séquence :

C B A

Solution:
Organisez la liste par ordre croissant :

A B C

Le moyen terme, B, est la médiane. C'est la grandeur qui se situe entre les deux autres grandeurs.

La recherche de la médiane dans une liste n'est pas de ce genre. Par exemple, dans une liste de 19 éléments non triés, la médiane du premier élément, du milieu et du dernier élément peut être requise. Ces trois valeurs peuvent ne pas être dans l'ordre croissant ; et donc, leurs indices doivent être pris en considération.

Avec Quick Sort, la médiane de l'ensemble de la liste et des sous-listes est requise. Le pseudocode pour rechercher la médiane de trois valeurs espacées dans une liste (tableau) est :

Le terme arr signifie tableau. Ce segment de code recherche la médiane et effectue également un tri. Ce segment de code semble simple, mais il peut être assez déroutant. Alors, faites attention à l'explication suivante:

Le tri dans ce didacticiel produira une liste où la première valeur est la plus petite valeur et la dernière valeur est la plus grande valeur. Avec l'alphabet, A est inférieur à Z.

Ici, le pivot est la médiane résultante. Low est l'indice le plus bas de la liste ou de la sous-liste (pas nécessairement pour la valeur la plus basse) ; high est l'indice le plus élevé de la liste ou de la sous-liste (pas nécessairement pour la valeur la plus élevée), et middle est l'indice médian conventionnel (pas nécessairement pour la valeur médiane de toute la liste).

Ainsi, la médiane à obtenir se situe entre la valeur de l'indice le plus bas, la valeur de l'indice médian et la valeur de l'indice le plus élevé.

Dans le code, l'indice médian conventionnel est obtenu en premier. A ce début, la liste n'est pas triée. La comparaison et un certain réarrangement dans l'ordre croissant des trois valeurs doivent avoir lieu en même temps. La première instruction if compare la valeur de l'index le plus bas et celle de l'index du milieu. Si celle de l'indice médian est inférieure à celle de l'indice le plus bas, alors les deux valeurs échangent leurs positions. Cela commence le tri et modifie la disposition des valeurs dans la liste ou la sous-liste. La deuxième instruction if compare la valeur de l'index le plus élevé et celle de l'index le plus bas. Si celle de l'indice le plus élevé est inférieure à celle de l'indice le plus faible, les deux valeurs échangent leurs positions. Cela entraîne un certain tri et une modification de l'agencement des valeurs dans la liste ou la sous-liste. La troisième instruction if compare la valeur de l'index du milieu et celle de l'index le plus élevé. Si celle de l'indice le plus élevé est inférieure à l'indice médian, les deux valeurs échangent leurs positions. Certains tris ou réarrangements peuvent également se produire ici. Cette troisième condition if n'est pas comme les deux précédentes.

A la fin de ces trois swaps, la valeur médiane des trois valeurs en question serait A[high], dont le contenu original aurait pu être modifié dans le segment de code. Par exemple, considérons la séquence non triée :

C B A

Nous savons déjà que la médiane est B. Cependant, cela doit être prouvé. Le but ici est d'obtenir la médiane de ces trois valeurs en utilisant le segment de code ci-dessus. La première instruction if compare B et C. Si B est inférieur à C, les positions de B et C doivent être permutées. B est inférieur à C, donc le nouvel arrangement devient :

B C A

Remarquez que les valeurs de l'index le plus bas et de l'index du milieu ont changé. La deuxième instruction if compare A et B. Si A est inférieur à B, alors les positions de A et B doivent être échangées. A est inférieur à B, donc le nouvel arrangement devient :

A C B

Remarquez que les valeurs de l'index le plus élevé et de l'index le plus bas ont changé. La troisième instruction if compare C et B. Si C est inférieur à B, alors les positions de C et B doivent être échangées. C n'est pas inférieur à B, donc aucun échange n'a lieu. La nouvelle disposition reste la même que la précédente, c'est-à-dire :

A C B

B est la médiane, c'est-à-dire A[élevé], et c'est le pivot. Ainsi, le pivot naît à l'extrémité de la liste ou de la sous-liste.

La fonction d'échange

Une autre fonctionnalité requise par Quick Sort est la fonction d'échange. La fonction d'échange, échange les valeurs de deux variables. Le pseudocode de la fonction d'échange est :

Ici, x et y font référence aux valeurs réelles et non aux copies.

Le tri dans cet article produira une liste où la première valeur est la plus petite valeur et la dernière valeur est la plus grande valeur.

Contenu de l'article

• Algorithme de tri rapide
• Un pseudo-code de partition
• Illustration du tri rapide
• Codage Java
• Conclusion

Algorithme de tri rapide

La manière normale de trier une liste non triée consiste à considérer les deux premières valeurs. S'ils ne sont pas en ordre, mettez-les en ordre. Ensuite, considérez les trois premières valeurs. Scannez les deux premiers pour voir où se situe la troisième valeur et ajustez-la de manière appropriée. Ensuite, considérez les quatre premières valeurs. Scannez les trois premières valeurs pour voir où se situe la quatrième valeur et ajustez-la de manière appropriée. Continuez cette procédure jusqu'à ce que toute la liste soit triée.

Cette procédure, également connue sous le nom de tri par force brute, dans le jargon de la programmation informatique, est trop lente. L'algorithme de tri rapide est livré avec une procédure beaucoup plus rapide.

Les étapes de l'algorithme de tri rapide sont les suivantes :

1. Assurez-vous qu'il y a au moins 2 numéros à trier dans la liste non triée.
2. Obtenez une valeur centrale estimée pour la liste, appelée pivot. La médiane, telle que décrite ci-dessus, est une façon d'obtenir le pivot. Différentes façons viennent avec leurs avantages et leurs inconvénients. - Voir plus tard.
3. Partitionner la liste. Cela signifie, placez le pivot dans la liste. De cette manière, tous les éléments de gauche sont inférieurs à la valeur pivot, et tous les éléments de droite sont supérieurs ou égaux à la valeur pivot. Il existe différentes manières de partitionner. Chaque méthode de partition a ses avantages et ses inconvénients. Le partitionnement se divise dans le paradigme diviser pour régner.
4. Répétez les étapes 1, 2 et 3 de manière récursive pour les nouvelles paires de sous-listes qui émergent jusqu'à ce que toute la liste soit triée. C'est conquérant dans le paradigme diviser pour régner.

Le pseudo-code de tri rapide est :

Un pseudo-code de partition

Le pseudocode de partition utilisé dans ce tutoriel est :

Dans l'illustration du tri rapide ci-dessous, ce code est utilisé :

Illustration du tri rapide

Considérez la liste non triée (tableau) de lettres alphabétiques suivante :

Q W E R T Y U I O P

Par inspection, la liste triée est :

E I O P Q R T U W Y

La liste triée va maintenant être prouvée, en utilisant l'algorithme ci-dessus et les segments de pseudocode, à partir de la liste non triée :

Q W E R T Y U I O P

Le premier pivot est déterminé à partir de arr[0]=Q, arr[4]=T et arr[9]=P, et est identifié comme Q et placé à l'extrême droite de la liste. Ainsi, la liste avec n'importe quel tri de fonction pivot devient :

P W E R T Y U I O Q

Le pivot actuel est Q. La procédure de pivot a fait quelques petits tris et a placé P en première position. La liste résultante doit être réorganisée (partitionnée), de telle sorte que tous les éléments de gauche aient une valeur plus petite, puis le pivot et tous les éléments à droite du pivot soient égaux ou supérieurs au pivot. L'ordinateur ne peut pas faire de partitionnement par inspection. Ainsi, il le fait en utilisant les index et l'algorithme de partition ci-dessus.

Les index bas et haut sont maintenant 0 et 9. Ainsi, l'ordinateur va commencer par scanner à partir de l'index 0 jusqu'à ce qu'il atteigne un index, dont la valeur est égale ou supérieure au pivot et s'y arrête temporairement. Il scrutera également à partir de l'extrémité haute (droite), l'indice 9, descendant, jusqu'à ce qu'il atteigne un indice dont la valeur est inférieure ou égale au pivot et s'y arrête temporairement. Cela signifie deux positions d'arrêt. Si i, la variable d'indice incrémentale, à partir du bas n'est pas encore égale ou supérieure à la variable d'indice décroissante, j à partir du haut, alors ces deux valeurs sont permutées. Dans la situation actuelle, le balayage des deux extrémités s'est arrêté à W et O. La liste devient donc :

P O E R T Y U I W Q

Le pivot est toujours Q. Le balayage dans des directions opposées continue et s'arrête en conséquence. Si i n'est pas encore égal ou supérieur à j, alors les deux valeurs auxquelles le balayage des deux extrémités s'est arrêté sont échangées. Cette fois, le balayage des deux extrémités s'est arrêté à R et I. Ainsi, l'arrangement de la liste devient :

P O E I T Y U R W Q

Le pivot est toujours Q. Le balayage dans des directions opposées continue et s'arrête en conséquence. Si i n'est pas encore égal ou supérieur à j, alors les deux valeurs auxquelles le balayage s'est arrêté sont permutées. Cette fois, le balayage des deux extrémités s'est arrêté à T pour i et I pour j. i et j se sont rencontrés ou croisés. Donc, il ne peut y avoir d'échange. La liste reste la même que :

P O E I T Y U R W Q

A ce stade, le pivot Q doit être placé dans sa position finale dans le tri. Cela se fait en échangeant arr[i] avec arr[high], en échangeant T et Q. La liste devient :

P O E I Q Y U R W T

À ce stade, le partitionnement de toute la liste est terminé. Le pivot = Q a joué son rôle. Il y a maintenant trois sous-listes, qui sont :

P O E I Q Y U R W T

La partition est division et conquête (tri) dans le paradigme. Q est à sa position de tri correcte. Chaque élément à gauche de Q est plus petit que Q, et chaque élément à droite de Q est plus grand que Q. Cependant, la liste de gauche n'est toujours pas triée ; et la bonne liste n'est toujours pas triée. Toute la fonction Quick Sort doit être appelée de manière récursive afin de trier la sous-liste de gauche et la sous-liste de droite. Ce rappel de Quick Sort doit se poursuivre ; de nouvelles sous-listes se développeront jusqu'à ce que toute la liste originale soit complètement triée. Pour chaque rappel de la fonction de tri rapide, la sous-liste de gauche est traitée en premier avant la sous-liste de droite correspondante. Un nouveau pivot doit être obtenu pour chaque sous-liste.

Pour la sous-liste :

P O E I

Le pivot (médiane) pour P, O et I est déterminé. Le pivot serait O. Pour cette sous-liste, et relative à la liste complète, le nouveau arr[low] est arr[0], et le nouveau arr[high] est le dernier arr[i-1] = arr[ 4-1] = arr[3], où i est l'indice de pivot final de la partition précédente. Après l'appel de la fonction pivot(), la nouvelle valeur pivot, pivot = O. Ne pas confondre entre la fonction pivot et la valeur pivot. La fonction pivot peut faire quelques petits tris et placer le pivot à l'extrême droite de la sous-liste. Cette sous-liste devient,

I P E O

Avec ce schéma, le pivot se termine toujours à l'extrémité droite de la sous-liste ou de la liste après son appel de fonction. Le balayage des deux extrémités commence à partir de arr[0] et arr[3] jusqu'à ce que i et j se rencontrent ou se croisent. La comparaison se fait avec pivot = O. Les premiers arrêts sont en P et E. Ils sont intervertis, et la nouvelle sous-liste devient :

Je E P O

Le balayage des deux extrémités se poursuit et les nouveaux arrêts sont en P pour i et en E pour j. Maintenant, je et j'ai rencontré ou croisé. La sous-liste reste donc la même que :

Je E P O

Le partitionnement d'une sous-liste ou d'une liste se termine lorsque le pivot a été placé dans sa position définitive. Ainsi, les nouvelles valeurs pour arr[i] et arr[high] sont échangées. C'est-à-dire que P et O sont échangés. La nouvelle sous-liste devient :

I E O P

O est maintenant à sa position finale pour toute la liste. Son rôle de pivot est terminé. La sous-liste est actuellement partitionnée en trois autres listes, qui sont :

I E O P

À ce stade, le tri rapide de la première sous-liste de droite doit être appelé. Cependant, il ne sera pas appelé. Au lieu de cela, il sera noté et réservé, pour être appelé plus tard. Au fur et à mesure que les instructions de la fonction de partitionnement étaient en cours d'exécution, depuis le haut de la fonction, c'est le Quick Sort pour la sous-liste de gauche qui doit être appelé maintenant (après l'appel de pivot()). Il sera appelé pour la liste :

C'EST À DIRE

Il commencera par chercher la médiane de I et E. Ici, arr[low] = I, arr[mid] = I et arr[high] = E. Donc la médiane, pivot, doit être déterminée par l'algorithme de pivot comme , I. Cependant, le pseudocode pivot ci-dessus déterminera le pivot comme E. Cette erreur se produit ici car le pseudocode ci-dessus est destiné à trois éléments et non à deux. Dans l'implémentation ci-dessous, il y a quelques ajustements au code. La sous-liste devient,

E je

Le pivot se termine toujours à l'extrémité droite de la sous-liste ou de la liste après son appel de fonction. Le balayage des deux extrémités commence à partir de arr[0] et arr[1] jusqu'à ce que i et j se rencontrent ou se croisent. La comparaison se fait avec pivot = I. Les premiers et seuls arrêts sont en I et E : en I pour i et en E pour j. Maintenant, je et j'ai rencontré ou croisé. Ainsi, la sous-liste reste la même que :

E je

Le partitionnement d'une sous-liste ou d'une liste se termine lorsque le pivot a été placé dans sa position définitive. Ainsi, les nouvelles valeurs pour arr[i] et arr[high] sont échangées. Il arrive ici que arr[i] = I et arr[high] = I. Ainsi, la même valeur est échangée avec elle-même. La nouvelle sous-liste devient :

E je

I est maintenant à sa position finale pour toute la liste. Son rôle de pivot est terminé. La sous-liste est maintenant divisée en deux autres listes, qui sont,

E je

Maintenant, les pivots jusqu'à présent ont été Q, O et I. Les pivots se terminent à leurs positions finales. Une sous-liste d'un seul élément, comme le P ci-dessus, se termine également à sa position finale.

À ce stade, la première sous-liste de gauche a été complètement triée. Et la procédure de tri est désormais à :

E I O P Q Y U R W T

La première sous-liste à droite :

Y U R W T

doit encore être trié.

Conquérir la première sous-liste de droite
N'oubliez pas que l'appel de tri rapide pour la première sous-liste de droite a été noté et réservé au lieu d'être exécuté. À ce stade, il sera exécuté. Et ainsi, le nouveau arr[low] = arr[5] = arr[QPivotIndex+1], et le nouveau arr[high] reste arr[9]. Un ensemble similaire d'activités qui se sont produites pour la première sous-liste de gauche se produira ici. Et cette première sous-liste de droite est triée en :

R T U W Y

Et la liste non triée d'origine a été triée comme suit :

E I O P Q R T U W Y

Codage Java

Mettre l'algorithme en Java consiste simplement à mettre tous les segments de pseudocode ci-dessus dans des méthodes Java dans une seule classe. N'oubliez pas qu'il doit y avoir une méthode main() dans la classe qui appellera la fonction quicksort() avec le tableau non trié.

La méthode pivot()

La méthode Java pivot() qui renvoie la valeur, pivot, doit être :

La méthode swap()

La méthode swap() doit être :

La méthode quicksort()

La méthode quicksort() doit être :

La méthode partition()

La méthode partition() doit être :

La méthode main()

La méthode main() peut être :

Toutes les méthodes ci-dessus peuvent être regroupées dans une seule classe.

Conclusion

Quick Sort est un algorithme de tri qui utilise le paradigme diviser pour régner. Il commence par diviser une liste non triée en deux ou trois sous-listes. Dans ce didacticiel, Quick Sort a divisé une liste en trois sous-listes : une sous-liste de gauche, une liste du milieu d'un seul élément et une sous-liste de droite. Conquérir dans Quick Sort consiste à diviser une liste ou une sous-liste tout en la triant, à l'aide d'une valeur pivot. Ce didacticiel a expliqué une implémentation de Quick Sort dans le langage informatique Java.

A propos de l'auteur

Chrysanthus Forcha

Découvreur de mathématiques Intégration des Premiers Principes et séries connexes. Master en Enseignement Technique, spécialité Electronique et Logiciels Informatiques. B.Sc. Électronique. J'ai également des connaissances et une expérience au niveau Master en Informatique et Télécommunications. Sur 20 000 écrivains, j'étais le 37e meilleur écrivain sur devarticles.com. Je travaille dans ces domaines depuis plus de 10 ans.

POSTES DE CONSEILS LINUX CONNEXES

• Comparer des chaînes en Java
• Comment utiliser HashMap en Java
• Tri rapide en Java expliqué
• Parcours de précommande d'arbre binaire en Java
• Fusionner le tri en Java expliqué
• Comment utiliser Scanner en Java
• Java écrire dans un fichier