Aller au contenu
Accueil » Trier vos tableaux en VBA avec QuickSort

Trier vos tableaux en VBA avec QuickSort

    tri quicksort récursif en vba

    Bonjour à tous,
    Je sais pas vous mais il m’arrive d’avoir besoin de trier mes tableaux en VBA. En effet, si vous avez besoin d’écrire vos données dans un ordre particulier ou que vous souhaitez travailler avec données triées pour optimiser votre programme, vous aurez besoin d’un algorithme de tri.

    Avant de présenter l’algorithme QuickSort, je vais d’abord vous présenter des algorithmes très simples qui fonctionnent très bien. Les deux exemples présentés vous permettront de trier un tableau suivant une colonne donnée dans l’ordre ascendant ou descendant. Ces exemples ne sont pas du tout optimisés en terme de performance mais ça fonctionne. Si vos données sont de petites tailles, il n’y a pas besoin de s’embêter avec des algorithmes plus complexes.

    Algorithme de tri ascendant

    Le programme va parcourir les lignes du tableau les unes après les autres. A chaque ligne, il va comparer les lignes en dessous. Si la valeur de la ligne active est supérieure à une ligne en dessous, on permute alors les lignes. Enfin, l’argument « intCol » permet d’identifier le numéro de la colonne qui est utilisée pour appliquer le tri.

    Vous noterez que les indices des tableaux comment à 0. En effet, j’ai pour habitude d’utiliser l’option « base 0 ». Avec cette option, au lieu de travailler sur des indices allant de 1 à N, les boucles travaillent de 0 à N-1. Cela me permet d’être cohérent avec mes programmes en Python et de ne pas me faire de noeuds au cerveau. Si vous ne souhaitez pas utiliser cette option, il faudra modifier le programme et décaler les indices.

    Function Tri2Dascendant(MyArray() As Variant, intCol As Integer)
    
        Dim i As Long, j As Long, k As Long, N As Long
        Dim Temp() As Variant
        
        N = UBound(MyArray, 2)
        ReDim Temp(N)
        
        'Sort the Array
        For i = 0 To UBound(MyArray, 1) - 1
            For j = i + 1 To UBound(MyArray, 1)
                If MyArray(i,intCol) > MyArray(j,intCol) Then
                    For k = 0 To N
                        Temp(k) = MyArray(j, k)
                        MyArray(j,k) = MyArray(i, k)
                        MyArray(i, k) = Temp(k)
                    Next
                End If
            Next j
        Next i
    
        Sort2dArrayDescending = MyArray
    End Function
    VB

    Algorithme de tri descendant

    C’est le même algorithme sauf que la condition est inversée.

    Function Tri2Ddescendant(MyArray() As Variant, intCol As Integer)
    
        Dim i As Long, j As Long, k As Long, N As Long
        Dim Temp() As Variant
        
        N = UBound(MyArray, 2)
        ReDim Temp(N)
        
        'Sort the Array
        For i = 0 To UBound(MyArray, 1) - 1
            For j = i + 1 To UBound(MyArray, 1)
                If MyArray(i,intCol) < MyArray(j,intCol) Then
                    For k = 0 To N
                        Temp(k) = MyArray(j, k)
                        MyArray(j,k) = MyArray(i, k)
                        MyArray(i, k) = Temp(k)
                    Next
                End If
            Next j
        Next i
    
        Sort2dArrayDescending = MyArray
    End Function
    VB

    L’algorithme QuickSort

    Maintenant que vous avez déjà un outil simple d’utilisation, passons à la vitesse supérieure et analysons l’algorithme QuickSort.

    Un peu d’histoire

    L’algorithme QuickSort est l’un des algorithmes les plus populaires et efficaces utilisés en informatique. C’est un algorithme de tri récursif inventé par le professeur Charles Antony Richard Hoare en 1961. Il est fondé sur la méthode de conception « divisé pour mieux régner ». Il fonctionne en choisissant un élément du tableau appelé « pivot ». Avec ce pivot, le tableau sera réordonné afin de déplacer tous les éléments inférieurs au pivot d’un côté et les éléments supérieurs au pivot de l’autre. Ainsi, le tableau et maintenant divisé en deux parties. La même opération est répétée de manière récursive jusqu’à ce que le tableau entier soit trié.

    Implémentation de l’algorithme QuickSort

    Voici le code pour utiliser l’algorithme QuickSort sur un tableau à une dimension avec des variables de type Entier. Vous pouvez modifier le code pour changer le type du tableau et même rajouter une dimension. L’algorithme est basé sur le programme décrit sur la page Wikipédia dédiée.

    Sub QuickSort(liste() As Integer, ByVal index_min As Long, ByVal index_max As Long)
     
        Dim pivot As Integer
        Dim id_sup As Long
        Dim id_inf As Long
        Dim index As Long
     
        ' S'il y a 0 ou 1 élément dans la liste, c'est déjà trié
        If index_min >= index_max Then Exit Sub
     
        ' Index pour le pivot et permutation
        ' une valeur aléatoire de maximiser les performances
        index = Int((index_max - index_min + 1) * Rnd + index_min)
        pivot = liste(index)
        liste(index) = liste(index_min)
     
        id_inf = index_min
        id_sup = index_max
        Do
            ' on cherche à partir de id_sup une valeur inférieure au pivot
            Do While liste(id_sup) >= pivot
                id_sup = id_sup - 1
                If id_sup <= id_inf Then Exit Do
            Loop
            If id_sup <= id_inf Then
                liste(id_inf) = pivot
                Exit Do
            End If
     
            ' on met la valeur de id_sup et id_inf
            liste(id_inf) = liste(id_sup)
     
            ' on cherche à partir de id_inf une valeur supériere au pivot
            id_inf = id_inf + 1
            Do While liste(id_inf) < pivot
                id_inf = id_inf + 1
                If id_inf >= id_sup Then Exit Do
            Loop
            If id_inf >= id_sup Then
                id_inf = id_sup
                liste(id_sup) = pivot
                Exit Do
            End If
     
            ' on met la valeur de id_inf dans id_sup
            liste(id_sup) = liste(id_inf)
        Loop
     
        ' Appel récursif sur les deux sous-tableaux
        QuickSort liste, index_min, id_inf - 1
        QuickSort liste, id_inf + 1, index_max
    End Sub
    VB

    Afin d’imager un peu le fonctionnement de l’algorithme, nous allons considérer que la valeur du pivot est la valeur médiane. Ceci sous-entend que le tableau sera donc divisé en deux parties partie égale. La première sera forcément inférieure au pivot et la seconde supérieure.

    illustration de l'algorithme QuickSort

    Pour conclure, l’algorithme QuickSort est vraiment efficace pour réaliser vos tris. Comme en VBA il n’y a pas de fonction (à ma connaissance) de tri, vous pourrez importer ce code pour avoir une solution rapide et efficace.

    N’hésitez pas à laisser un commentaire, j’y répondrai avec plaisir,
    A bientôt,
    Benjamin

    Si vous avez aimé l'article, vous êtes libres de le partager ! :)

    Laisser un commentaire

    Récupérez votre guide pour débuter en Python. Je vous offre plus de 80 pages pour partir sur de bonnes bases !