 |
Publicité 
|
Deuxième article d'une série de cinq présentant différentes méthodes de tri. Nous expliquons ici la méthode dite du "tri à bulle optimisé". Toutes ces procédures seront téléchargeables avec l'interface de comparaison (article 5).
Rappelons les cinq méthodes étudiées dans ces articles:
Le tri à bulle optimisé :
Les explications sont données pour le tri croissant.
Le principe ressemble à celui du tri à bulle, l'optimisation consiste à comparer un élément N par rapport à celui qui lui est supérieur dans le classement N + 1 (tri à bulle), on le décale tant que c'est possible.
On compare également l'enregistrement non classé M le plus lourd à celui qui lui est inférieur M - 1, on le décale tant que c'est possible.
De plus, un flag est mis en place, il indique qu'aucune modification n'a été apportée au classement, dès qu'il apparaît le tri s'arrête.
Source:
Sub Tri_A_Bulles_Optimise(ByVal Nb_Element As Long, Tableau() As Variant, ByVal Sens As Boolean)
' le paramètre Nb_Element correspond au nombre d'éléments du tableau, sa valeur n'est donc pas modifiée
' le paramètre Tableau() est le tableau à trier, il est modifié puis retourné
' le paramètre Sens est vrai pour un tri croissant
Dim Debut As Long
Dim Fin As Long
Dim I As Long
' I est une variable intermédiaire utilisée pour les compteurs de boucles
Dim Tampon_Fin As Long
' Tampon_Fin est une variable intermédiaire évitant de trier ce qui l'est déjà
Dim Termine As Boolean
' Termine est notre flag de fin de tri
Dim Ligne_Tampon As Variant
' Ligne_Tampon est une variable intermédiaire utilisée pour la permutation d'éléments
Debut = 1
Fin = Nb_Element - 1
Termine = False
' On tourne tant que l'on fait des modifications
Do While (Not Termine) And (Debut < Fin)
Termine = True
' On fait monter la première ligne autant que possible
For I = Debut To Fin
If (Tableau(I) > Tableau(I + 1) And Sens) Or (Tableau(I) < Tableau(I + 1) And Not Sens) Then
Ligne_Tampon = Tableau(I)
Tableau(I) = Tableau(I + 1)
Tableau(I + 1) = Ligne_Tampon
Termine = False
Tampon_Fin = I
End If
Next I
Fin = Tampon_Fin
If (Not Termine) Then
' On fait descendre le dernièr élément tant que possible
For I = Fin To Debut + 1 Step -1
If (Tableau(I) < Tableau(I - 1) And Sens) Or (Tableau(I) > Tableau(I - 1) And Not Sens) Then
Ligne_Tampon = Tableau(I)
Tableau(I) = Tableau(I - 1)
Tableau(I - 1) = Ligne_Tampon
Termine = False
Tampon_Fin = I
End If
Next I
End If
Loop
End Sub
|
