Tri à bulle, tri rapide (QuickSort)

Vous pouvez télécharger le classeur fc-pap-arrays qui illustre les exemples présentés sur les pages pas à pas traitant des arrays

Attention, le code présenté dans ce tutoriel et dans le classeur exemple a été écrit et vérifié avec la version 2010 d'excel. Certaines propriétés peuvent ne pas fonctionner avec des versions antérieures, et avec les versions Mac d'excel antérieures à 2011.
Merci d'utiliser les commentaires pour poser des questions directement en rapport avec CE tutoriel EXCLUSIVEMENT et de poser les questions sur vos développements particuliers sur le forum microsoft answers excel.

Pour classer des données dans un tableau, on peut bien entendu utiliser les fonctions de tri natives d'excel. Mais comment trier des données qui sont dans un array (donc en cours de traitement) ?
Ceci est utile dans de nombreuses circonstances, par exemple pour trier des données qui serviront de source dans une liste (combobox, listbox).
Voici 2 méthodes pour trier. La première, dite tri à bulles est facile à mettre en oeuvre mais ce n'est pas la plus rapide. La seconde est extrêmement rapide.
Vous verrez plus facilement la différence sur des tableaux de grande taille.

Tri à bulles pour un array à 1 dimension
Tri à bulles pour un array à 2 dimensions
Tri rapide (quick sort) pour un array à 1 dimension
Tri rapide (quick sort) pour un array à 2 dimensions

Tri à bulles

Le principe du tri à bulles est de comparer deux à deux les éléments d'un array. Si le premier élément est plus grand que le second (dans le cas d'un tri croissant), on inverse les deux valeurs. Sinon on passe à l'élément suivant. Cette méthode est répétée plusieurs fois sur tous les éléments de l'array jusqu'à ce qu'il n'y ait plus d'échanges entre deux positions.

Tri à bulles pour un array à une dimension

Sub triabulles1dim()
Dim T As Long
Dim i As Integer, j As Integer
Dim X As Integer, Y As Integer
Dim Tblo(1 To 500) As Integer

' Construction d'un array de 500 nombres aléatoires
For i = 1 To 500: Tblo(i) = Rnd * 100: Next
'si vous voulez vérifier, décommentez la ligne suivante
'Sheets("test").Range(Cells(1, 3), Cells(UBound(Tblo), 3)).Value = Application.WorksheetFunction.Transpose(Tblo)

T = Timer
'tri des nombres par ordre croissant
For i = 1 To 500
    For j = i To 500
        If Tblo(j) < Tblo(i) Then
            X = Tblo(i)
            Y = Tblo(j)
            Tblo(i) = Y
            Tblo(j) = X
        End If
    Next j
Next i
'Sheets("test").Range(Cells(1, 4), Cells(UBound(Tblo), 4)).Value = Application.WorksheetFunction.Transpose(Tblo)

Debug.Print Timer - T & " Secondes"

End Sub

Tri à bulles pour un array à deux dimensions

Sub triabulles2()
Dim T As Double
Dim Tblo
Dim Arr
Dim a As Long, b As Long, i As Long, j As Long
Dim X, Y

T = Timer
Tblo = Sheets("ex5-tri2").Range("A2:C36")

ReDim Arr(1 To UBound(Tblo, 1), 1 To UBound(Tblo, 2))
For i = 1 To UBound(Arr, 1)
  For j = 1 To UBound(Arr, 2)
      Arr(i, j) = Tblo(i, j)
  Next j
Next i

For a = 1 To UBound(Arr, 1)
    For b = a To UBound(Arr, 1)
    'Debug.Print Arr(a, 1)
    'Debug.Print Arr(b, 1)
        If Arr(b, 1) < Arr(a, 1) Then
            For j = 1 To UBound(Arr, 2)
                X = Arr(a, j)
                Y = Arr(b, j)
                'Debug.Print X & ";" & Y
                Arr(a, j) = Y
                Arr(b, j) = X
            Next j
        End If
     Next b
Next a

Sheets("ex5-tri2").Range("g2:i36") = Arr

MsgBox Timer - T & " secondes"
End Sub

Tri rapide (quickSort)

Le principe est proche de ce que nous avons vu dans la méthode pour inverser l'ordre d'une colonne d'un tableau. On choisit un élément "pivot", généralement une valeur médiane. On classe ensuite d'un coté les éléments plus petits que ce pivot et de l'autre ceux qui lui sont supérieurs. Sur chacun des deux sous groupes ainsi constitués, on recommence. Puis on recommence sur la 4 sous groupes... Et ainsi de suite de façon récursive jusqu'à ce que chaque sous-sous-sous... ensemble soit constitué d'un seul élément.
Cette méthode parait plus compliqué à comprendre mais le gain de temps est considérable lorsqu'il y a un grand nombre de données à trier.

Tri rapide (Quick sort) sur un array à une dimension

Sub trirapide1dim()
Dim T As Long
Dim i As Integer
Dim Tblo(1 To 500)
Dim Tmp(1 To 500) As Integer

' Construction de 500 nombres aléatoires
For i = 1 To 500: Tblo(i) = Rnd * 100: Next
'Sheets("test").Range(Cells(1, 3), Cells(UBound(Tblo), 3)).Value = Application.WorksheetFunction.Transpose(Tblo)

T = Timer
TriVite Tblo, LBound(Tblo), UBound(Tblo)
'Sheets("test").Range(Cells(1, 4), Cells(UBound(Tblo), 4)).Value = Application.WorksheetFunction.Transpose(Tblo)

Debug.Print Timer - T & " Secondes"
End Sub

Sub TriVite(MonArray(), Petit, Grand)
Dim Pivot
Dim p, g
Dim Temp

Pivot = MonArray((Petit + Grand) / 2)

p = Petit
g = Grand
While p <= g
    While MonArray(p) < Pivot
        p = p + 1
    Wend
    While Pivot < MonArray(g)
        g = g - 1
    Wend
    If p <= g Then
        Temp = MonArray(p)
        MonArray(p) = MonArray(g)
        MonArray(g) = Temp
        p = p + 1
        g = g - 1
    End If
Wend
If p < Grand Then Call TriVite(MonArray, p, Grand)
If Petit < g Then Call TriVite(MonArray, Petit, g)
End Sub

Tri rapide pour un array à deux dimensions

Sub TriRapide2()
Dim T As Long
Dim Tblo()

T = Timer
Tblo = Sheets("ex5-tri2").Range("A2:C36").Value
QuickSort2 Tblo, LBound(Tblo, 1), UBound(Tblo, 1)

Sheets("ex5-tri2").Range("G2:I36").Value = Tblo


MsgBox Timer - T & " Secondes"
End Sub

Sub QuickSort2(MonArray(), Petit, Grand)
Dim Pivot
Dim p, g
Dim j
Dim X

Pivot = MonArray((Petit + Grand) / 2, 1)

p = Petit
g = Grand
While p <= g
    While MonArray(p, 1) < Pivot
        p = p + 1
    Wend
    While Pivot < MonArray(g, 1)
        g = g - 1
    Wend
    If p <= g Then
        For j = 1 To UBound(MonArray, 2)
            X = MonArray(p, j)
            MonArray(p, j) = MonArray(g, j)
            MonArray(g, j) = X
        Next j
        p = p + 1
        g = g - 1
    End If
Wend
If p < Grand Then Call QuickSort2(MonArray, p, Grand)
If Petit < g Then Call QuickSort2(MonArray, Petit, g)
End Sub