Sort rapide dans Java expliqué

Quick Sort, également écrit comme Quicksort, est un schéma de tri de liste qui utilise le paradigme de division et de conquéraire. Il existe différents schémas pour un tri rapide, tous utilisant le paradigme de division et de conquéraire. Avant d'expliquer le tri rapide, le lecteur doit connaître la convention pour diviser de moitié une liste ou une sous-liste et la médiane de trois valeurs.

Convention de moitié

Lorsque le nombre d'éléments dans une liste est uniforme, la réduction de moitié de 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 moyen (milieu) de toute la liste, est le dernier élément de la première liste. Cela signifie que l'index moyen 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 moyen est 3 = 8/2 - 1.

Qu'en est-il du cas, lorsque le nombre d'éléments dans la liste ou le sous-liste est étrange? Au début, la longueur est toujours divisée par 2. Par convention, le nombre d'éléments dans la première moitié de cette division est la longueur / 2 + 1/2. Le comptage d'index commence à partir de zéro. L'indice moyen 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 moyen 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 central de toute la liste est le troisième élément de l'index, 2, qui est l'index moyen car le comptage d'index commence à partir de 0.

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

Médiane de trois valeurs

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

C B A

Solution:
Organiser la liste dans l'ordre croissant:

A B C

Le moyen terme, b, est la médiane. C'est l'ampleur qui se situe entre les deux autres amplitudes.

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

Avec un tri rapide, la médiane de toute la liste et les sous-listes est requise. Le pseudocode pour rechercher la médiane de trois valeurs espacées dans une liste (tableau) est:

MID: = ⌊ (faible + haut) / 2⌋
Si arr [mid] < arr[low]
échanger arr [bas] avec arr [mid]
Si arr [high] < arr[low]
échanger arr [bas] avec arr [high]
Si arr [mid] < arr[high]
échanger arr [mid] avec arr [high]
pivot: = arr [high]

Le terme «arr» signifie tableau. Ce segment de code recherche la médiane et fait é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 tutoriel 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 qui en résulte. 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 du sous-liste (pas nécessairement pour la valeur la plus élevée), et le milieu est l'indice moyen conventionnel (pas nécessairement pour la valeur moyenne de toute la liste).

Ainsi, la médiane à obtenir est entre la valeur de l'index le plus bas, la valeur de l'index moyen et la valeur de l'indice le plus élevé.

Dans le code, l'index moyen conventionnel est obtenu en premier. À 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. Le premier statement IF compare la valeur de l'index le plus bas et celui de l'index moyen. Si celui de l'indice moyen est inférieur à celui de l'index le plus bas, alors les deux valeurs échangent des positions. Cela commence à trier et modifie la disposition des valeurs dans la liste ou la sous-liste. Le deuxième statement IF compare la valeur de l'indice le plus élevé et celui de l'indice le plus bas. Si celui de l'indice le plus élevé est inférieur à celui de l'indice le plus bas, les deux valeurs échangent des positions. Cela perpétue un tri et un changement de la disposition des valeurs dans la liste ou la sous-liste. Le troisième statement IF compare la valeur de l'index moyen et celui de l'indice le plus élevé. Si celui de l'indice le plus élevé est inférieur à l'indice central, les deux valeurs échangent des positions. Un tri ou un réarrangement peut également se produire ici. Ce troisième si-condition n'est pas comme les deux précédents.

À la fin de ces trois échanges, la valeur moyenne des trois valeurs en question serait un [haut], dont le contenu d'origine aurait pu être modifié dans le segment de code. Par exemple, considérez la séquence non triée:

C B A

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

B c a

Remarque, les valeurs de l'index le plus bas et de l'indice moyen ont changé. Le deuxième statement 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

Remarque, les valeurs de l'indice le plus élevé et de l'indice le plus bas ont changé. Le troisième statement 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. Le nouvel arrangement reste le précédent, c'est-à-dire:

A C B

B est la médiane, qui est, un [haut], et c'est le pivot. Ainsi, le pivot est né à l'extrémité extrême de la liste ou du sous-liste.

La fonction d'échange

Une autre fonctionnalité nécessaire par un tri rapide est la fonction d'échange. La fonction d'échange, échange les valeurs de deux variables. Le pseudocode pour la fonction d'échange est:

Définir l'échange (x, y)
Temp: = x
x: = y
y: = temp

Ici, x et y se réfèrent aux valeurs réelles et non aux copies.

Le tri de 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
• Une pseudocode de partition
• Illustration de tri rapide
• Codage java
• Conclusion

Algorithme de tri rapide

La façon normale de trier une liste non triée est de 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ù la troisième valeur s'adapte et s'adapte de manière appropriée. Ensuite, considérez les quatre premières valeurs. Scannez les trois premières valeurs pour voir où la quatrième valeur s'adapte et s'adapte de manière appropriée. Continuez avec cette procédure jusqu'à ce que toute la liste soit triée.

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

Les étapes de l'algorithme QuickSort sont les suivantes:

1. Assurez-vous qu'il y a au moins 2 numéros à trier dans la liste non triée.
2. Obtenir une valeur centrale estimée à la liste, appelée le pivot. La médiane, comme décrit ci-dessus, est un moyen 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 de pivot, et tous les éléments à droite sont supérieurs ou égaux à la valeur de pivot. Il existe différentes façons de partitionner. Chaque méthode de partition est livrée avec ses avantages et ses inconvénients. Le partitionnement se divise dans le paradigme de division et de conquéraire.
4. Répétez les étapes 1, 2 et 3 récursivement pour les nouvelles paires de sous-liste qui émergent jusqu'à ce que toute la liste soit triée. Ceci est conquérant dans le paradigme de division et de conquéraire.

Le pseudocode de tri rapide est:

algorithme Quicksort (arr, bas, haut) est
Je coule < high then
pivot (bas, haut)
p: = partition (arr, bas, haut)
Quicksort (Arr, Low, P - 1)
Quicksort (Arr, P + 1, High)

Une pseudocode de partition

Le pseudocode de partition utilisé dans ce tutoriel est:

La partition d'algorithme (Arr, Low, High) est
pivot: = arr [high]
i: = bas
J: = haut
faire
faire
++je
Pendant (arr [i] < pivot)
faire
--J
tandis que (arr [j]> pivot)
si je < j)
échanger arr [i] avec arr [j]
alors que je < j)
échanger arr [i] avec arr [high]
retour i

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

Illustration de tri rapide

Considérez la liste (tableau) des lettres alphabétiques suivantes suivantes:

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 sera désormais 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 l'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 tout 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 un petit tri et a placé P en première position. La liste résultante doit être réorganisée (partitionnée), de sorte que tous les éléments de gauche sont en valeur plus faible, puis le pivot et tous les éléments à droite du pivot, sont égaux ou supérieurs au pivot. L'ordinateur ne peut pas faire de partitionné par inspection. Donc, il le fait en utilisant les index et l'algorithme de partition ci-dessus.

Les indices bas et élevés sont désormais 0 et 9. Ainsi, l'ordinateur commencera par numériser à partir de l'index 0 jusqu'à ce qu'il atteigne un index, dont la valeur est égale ou supérieure au pivot et s'arrête temporairement. Il scannera également à partir de l'extrémité élevée (droite), index 9, en baisse, jusqu'à ce qu'il atteigne un index dont la valeur est inférieure ou égale au pivot et s'arrête temporairement. Cela signifie deux positions d'arrêt. Si i, la variable d'indice incrémentielle, à partir de faible, n'est pas encore égale ou supérieure à la variable d'index décroissante, J de High, alors ces deux valeurs sont échangées. Dans la situation actuelle, la numérisation des deux extrémités s'est arrêtée à 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 se poursuit et s'arrête en conséquence. Si je 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é est échangé. Cette fois, la numérisation des deux extrémités s'est arrêtée à R et je. 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 se poursuit et s'arrête en conséquence. Si je n'est pas encore égal ou supérieur à J, alors les deux valeurs auxquelles le balayage s'est arrêté, sont échangés. Cette fois, la numérisation des deux extrémités s'est arrêtée à T pour I et I pour J. Moi et j ai rencontré ou croisé. 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

À 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], é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 la division et la 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 de tri rapide doit être appelée récursivement afin de trier la sous-liste gauche et la sous-liste droite. Ce rappel du type rapide doit continuer; Les nouveaux 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 gauche est prise en compte avant que la sous-liste droite correspondante ne soit prise. Un nouveau pivot doit être obtenu pour chaque sous-liste.

Pour la sous-liste:

P o e i

Le pivot (médian) pour P, O et I est déterminé. Le pivot serait o. Pour ce sous-liste, et relatif à la liste complète, le nouvel arr [Low] est Arr [0], et le nouvel 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. Une fois la fonction pivot () appelée, la nouvelle valeur de pivot, pivot = o. Ne confondez pas entre la fonction de pivot et la valeur de pivot. La fonction pivot peut faire un petit tri et placer le pivot à l'extrême droite de la sous-liste. Ce 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. La numérisation des deux extrémités commence à ARR [0] et ARR [3] jusqu'à ce que I et J se rencontrent ou croisent. La comparaison se fait avec pivot = o. Les premiers arrêts sont à P et E. Ils sont échangés et le nouveau sous-liste devient:

I e p o

La numérisation des deux extrémités se poursuit, et les nouveaux arrêts sont à P pour I et à E pour J. Maintenant moi et j ai rencontré ou croisé. Ainsi, la sous-liste reste la même que:

I e p o

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

I e o p

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

I e o p

À ce stade, une sorte rapide de la première sous-liste à droite doit être appelée. Cependant, il ne sera pas appelé. Au lieu de cela, il sera noté et réservé, pour être appelé plus tard. Comme les déclarations de la fonction de partitionnement étaient en cours d'exécution, du haut de la fonction, c'est le tri rapide de la sous-liste gauche qui doit être appelée maintenant (après que Pivot () a été appelé). Il sera appelé pour la liste:

C'EST À DIRE

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

E i

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

E i

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

E i

Je suis maintenant à sa position finale pour toute la liste. Son rôle de pivot a pris fin. Le sous-liste est désormais partitionné en deux autres listes, qui sont,

E i

Maintenant, les pivots jusqu'à présent ont été Q, O et I. Les pivots se terminent à leurs positions finales. Un 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 gauche a été complètement triée. Et la procédure de tri est maintenant à:

E i o p q y u r w t

Le premier sous-liste de droite:

Y u r w t

doit encore être trié.

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

R t u w y

Et la liste originale non triée a été triée:

E i o p q r t u w y

Codage java

Mettre l'algorithme en Java, c'est simplement mettre tous les segments de pseudocode ci-dessus dans les méthodes Java dans une seule classe. N'oubliez pas qu'il doit y avoir une méthode principale () 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, devrait être:

vide pivot (char arr [], int bas, int high)
int mid = (bas + haut) / 2;
if (arr [mid] < arr[low])
échange (arr, bas, mid);
if (arr [high] < arr[low])
échange (arr, bas, haut);
if ((haut - bas)> 2)
if (arr [mid] < arr[high])
échange (Arr, Mid, High);

La méthode swap ()

La méthode swap () doit être:

VOID Swap (char arr [], int x, int y)
char Temp = arr [x];
arr [x] = arr [y];
arr [y] = temp;

La méthode Quicksort ()

La méthode Quicksort () doit être:

void Quicksort (char arr [], int bas, int high)
Je coule < high)
pivot (arr, bas, haut);
int p = partition (arr, bas, haut);
Quicksort (arr, bas, p - 1);
Quicksort (Arr, P + 1, High);

La méthode de partition ()

La méthode de partition () doit être:

int partition (char arr [], int low, int high)
char pivot = arr [high];
int i = bas;
int j = high;
faire
faire
++je;
Pendant (arr [i] < pivot);
faire
--J;
while (arr [j]> pivot);
si je < j)
échange (arr, i, j);
alors que je < j);
échange (arr, i, haut);
retour i;

La méthode principale ()

La méthode principale () peut être:

public static void main (String [] args)
char arr [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
Theclass Quicksort = new theclass ();
Tri rapide.Quicksort (arr, 0, 9);
Système.dehors.println ("Les éléments triés:");
pour (int i = 0; i<10; i++)
Système.dehors.print (arr [i]); Système.dehors.imprimer(");

Système.dehors.println ();

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

Conclusion

Quick Syt est un algorithme de tri qui utilise le paradigme de division et de conquéraire. Il commence par diviser une liste non triée en deux ou trois sous-listes. Dans ce tutoriel, Quick Syt a divisé une liste en trois sous-listes: une sous-liste gauche, une liste intermédiaire d'un seul élément et une sous-liste droite. La conquête en tri rapide divise une liste ou une sous-liste lors de la tri, en utilisant une valeur de pivot. Ce didacticiel a expliqué une implémentation du type rapide dans le langage informatique Java.