|
|
Auteur : Eric PETIT
|
Dernier article d'une série de cinq présentant différentes méthodes de tri. Nous expliquons ici la méthode dite du "tri rapide" (Quick Sort). Toutes ces procédures seront téléchargeables avec l'interface de comparaison.
Rappelons les cinq méthodes étudiées dans ces articles:
- le tri à bulle
- le tri à bulle optimisé - le tri dichotomique - le tri par la méthode de Shell Metzner - le tri rapide (Quick Sort) Le tri rapide (Quick Sort) :
Les explications sont données pour le tri croissant.
Cette méthode est la plus rapide des cinq, cependant, cette fonction étant récurrente, elle utilise plus de ressources que la méthode de Shell Mezner.
Le principe consiste à faire un tri par rapport à un élément du tableau, les plus lourd d'un coté, les autres de l'autre.
On recommence ensuite pour chacun de ces cotés et ainsi de suite... Cette procédure s'appelle elle-même, elle est récurrente. Source:
Sub Tri_QuickSort(Debut As Long, Fin As Long, Tableau() As Variant, ByVal Sens As Boolean)
' le paramètre Debut correspond au numéro du premier élément à trier (à l'appel il vaut 1)
' le paramètre Fin correspond au numéro du dernier élément à trier (à l'appel il vaut Nb_Element) ' le paramètre Tableau() est le tableau à trier, il est modifié puis retourné ' le paramètre Sens est vrai pour un tri croissant Dim I As Long
Dim J As Long ' I et J sont des variables intermédiaires utilisées pour les compteurs de boucles Dim Ligne_Milieu As Variant ' Ligne_Milieu est une variable intermédiaire utilisée pour la comparaison d'éléments Dim Ligne_Tampon As Variant ' Ligne_Tampon est une variable intermédiaire utilisée pour la permutation d'éléments I = Debut
J = Fin Ligne_Milieu = Tableau((Debut + Fin) 2) Do
If Sens Then
While Tableau(I) < Ligne_Milieu
I = I + 1
Wend
While Ligne_Milieu < Tableau(J) J = J - 1
Wend
Else
While Tableau(I) > Ligne_Milieu
I = I + 1
Wend
While Ligne_Milieu > Tableau(J) J = J - 1
Wend
End If
If I <= J Then Ligne_Tampon = Tableau(I)
Tableau(I) = Tableau(J) Tableau(J) = Ligne_Tampon I = I + 1 J = J - 1 End If
Loop Until I > J
' Une fois le tri précédant effectué, on rappelle la fonction en changeant les bornes. If Debut < J Then Tri_QuickSort Debut, J, Tableau(), Sens
End If
If I < Fin Then Tri_QuickSort I, Fin, Tableau(), Sens
End If
End Sub
|