Question 151

Comment trier des données en VB ? Quelles sont les différentes méthodes de tri ?

Introduction

Trier des données est une des problématiques les plus fréquentes en programmation : quels que soient le genre de programmes qu'il écrit, tout programmeur est un jour confronté à devoir trier des données. Pour ce faire, on a développé au fil des années de très nombreuses méthodes de tris, adaptées à toute sortes de situations et contraintes (temps, espace mémoire, parallélisation, etc.).

Le but de cet article est de présenter quelques uns des algorithmes de tri les plus classiques, avec pour chacun une implémentation type et une courte notice expliquant ses avantages et ses inconvénients.
Cet article ne prétend pas être un cours d'algorithmique, pas plus qu'il ne prétend exposer "toutes" les méthodes de tris : des livres entiers ont été écrits sur le sujet. Nous donnerons d'ailleurs quelques références utiles à la fin de l'article dans la section "Aller plus loin".

Nous présentons ici quelques méthodes, les plus classiques ou les plus connues :

La section Méthodes alternatives présente brièvement quelques autres façons possibles de trier : utilisation de base de données et de SQL, ListBox.

Quelques algorithmes de tri et leurs implémentations

Dans tout ce qui suit, on notera N le nombre d'éléments du tableau à trier. Toutes les implémentations qui sont données ici sont des implémentations simples, ou l'on a pas recherché d'optimisations particulières. Ces algorithmes sont implémentés de la façon la plus classique et la plus compréhensible possible; on trouvera à la fin de cet article, dans la section "Aller plus loin", des liens proposant des implémentations optimisées de ces algorithmes. Ils utilisent tous des tableaux où les éléments sont de type Long, on pourra remplacer ce type par le type voulu si nécessaire.

Le Tri par comptage (comparatif) (Comparison Counting Sort)

Le tri par comptage ou "Counting Sort" est particulier, en ce sens qu'il ne trie pas le tableau lui même mais qu'il construit un second tableau qui va contenir les positions triées. L'algorithme présenté ici est le "Comparison Couting Sort"; C'est un algorithme très peu efficace. Qui plus est, il a une très mauvaise propriété : même quand le tableau est déjà entièrement trié, son temps d'exécution reste le même. Cependant, il est original et peut avoir des applications, pour N petit. A noter qu'il existe un autre algorithme de tri par comptage, le "Distribution Counting Sort", dont la description dépasse le cadre de cet article généraliste.

'  
' Tri par comptage - Countring Sort  
'  
Public Sub CountingSort(t() As Long, count() As Long, _   
                        Optional ByVal loBound As Long = -1, _   
                        Optional ByVal upBound As Long = -1)   
                               
    Dim i As Long, j As Long   
       
    If loBound = -1 Then   
        loBound = LBound(t())   
    End If   
    If upBound = -1 Then   
        upBound = UBound(t())   
    End If   

    ReDim count(loBound To upBound)   
    For i = upBound To loBound Step -1   
        count(i) = loBound   
    Next i   
    For i = upBound To loBound Step -1   
        For j = i - 1 To loBound Step -1   
            If t(i) < t(j) Then   
                count(j) = count(j) + 1   
            Else   
                count(i) = count(i) + 1   
            End If   
        Next j   
    Next i   
End Sub

Le Tri par insertion naïf (Insertion Sort)

Il y a toute une famille de tris dits "tris par insertions". Certains de ces tris, comme celui-ci, ont des performances médiocres voire mauvaises alors que des variantes comme le "Tri de Shell" sont extrêmement efficaces.
Le principe ici est de trier le tableau un peu à la façon dont un joueur de carte trie les cartes qu'il a en main : il examine chaque carte en partant de la deuxième sur la gauche et l'insère à la bonne position. Ceci fait, il passe à la suivante à droite, et ainsi de suite jusqu'à la fin.
Cet algorithme est peu performant dans le pire des cas (données triées à l'envers), mais quand le tableau est déjà partiellement ordonné, cette méthode peut être assez efficace.
On retiendra parmi les avantages que cet algorithme est extrêmement court, et simple à implémenter dans n'importe quel langage.

'  
' Tri par insertion (naïf) - Insertion Sort  
'  
Public Sub InsertionSort(t() As Long, _   
                        Optional ByVal loBound As Long = -1, _   
                        Optional ByVal upBound As Long = -1)   
                                   
    Dim i As Long, j As Long, v As Long   
       
    If loBound = -1 Then   
        loBound = LBound(t())   
    End If   
    If upBound = -1 Then   
        upBound = UBound(t())   
    End If   
       
    For i = loBound + 1 To upBound   
        v = t(i): j = i   
        While t(j - 1) > v   
            t(j) = t(j - 1): j = j - 1   
        Wend   
        t(j) = v   
    Next i   
End Sub

Le Tri à bulle (Bubble Sort)

C'est certainement le plus connu et le plus sympathique des algorithmes "naïfs"! Son fonctionnement est très simple : on compare les éléments adjacents dans l'ordre, 2 à 2 du premier au dernier, et si ils ne sont pas ordonnés, on les échange. Puis on recommence du début, et ce tant qu'il y a eu au moins un échange.
Il doit donc son nom au fait que les éléments les plus grands "remontent", comme une bulle dans un tube rempli d'eau.
Parmi les inconvénients, on notera que les performances sont mauvaises dans le cas le plus défavorable (données triées à l'envers).
Mais il a aussi un certain nombre d'avantages : il est très simple à implémenter, très simple à adapter à des tris plus exotiques. Enfin, et c'est à signaler, il peut être très efficace quand le tableau est déjà "presque" trié.
Nous en donnons ici une implémentation simple mais il est très facile de l'améliorer (même si il reste inutilisable dès qu'il y a plus de quelques milliers d'éléments).

'  
' Tri à bulle  
'  
Public Sub BubbleSort(t() As Long, _  
                      Optional ByVal loBound As Long = -1, _  
                      Optional ByVal upBound As Long = -1)  
      
    Dim i As Long, tmp  As Long  
    Dim k As Long, test As Long  
      
    ' initialize bounds  
    If loBound = -1 Then  
        loBound = LBound(t())  
    End If  
    If upBound = -1 Then  
        upBound = UBound(t())  
    End If  
      
    k = upBound  
    Do  
        test = 0  
        For i = loBound To k - 1  
            ' comparison  
            If t(i) > t(i + 1) Then  
                ' exchange  
                test = i  
                tmp = t(i)  
                t(i) = t(i + 1)  
                t(i + 1) = tmp  
            End If  
        Next i  
        k = test ' increase lower bound, improve performances  
    Loop While test  
End Sub

Ces tris ont l'avantage d'être simple à comprendre et à implémenter. Leur principale faiblesse est qu'ils sont peu performants quand le nombre d'éléments à trier devient grand (typiquement quelques centaines ou milliers d'éléments). On peut néanmoins les employer quand le nombre d'éléments est petit, ou quand on en fait une utilisation peu intensive. Les méthodes suivantes (tri de Shell, tri rapide, tri par arbre binaire) n'ont pas ce défaut, et peuvent être utilisées pour de grandes valeurs de N.

Le Tri de Shell (Shell Sort)

Sur le principe, le Tri de Shell (du nom de son inventeur, Donald L.Shell, qui l'a proposé en 1952) est un tri par insertion. Son fonctionnement est assez complexe, et la détermination exacte de son temps d'exécution est un problème compliqué. En pratique, c'est un algorithme extrêmement efficace. On peut l'utiliser pour trier des tableaux contenant des centaines de milliers de données.
Pour donner un ordre de grandeur, disons que l'on peut trier un tableau entièrement désordonné de 350.000 éléments en moins d'une seconde. Par comparaison, il faudrait plus de 7 heures à un tri à bulle pour faire le même travail (environ 28000 fois plus de temps!).

'  
' Tri de Shell - Shell Sort  
'  
Public Sub ShellSort(t() As Long, _  
                    Optional ByVal loBound As Long = -1, _  
                    Optional ByVal upBound As Long = -1)  
      
    Dim i As Long, j As Long, h As Long, v As Long  
      
    If loBound = -1 Then  
        loBound = LBound(t())  
    End If  
    If upBound = -1 Then  
        upBound = UBound(t())  
    End If  

    h = loBound  
    Do  
        h = 3 * h + 1  
    Loop Until h > upBound  
      
    Do  
        h = h / 3  
        For i = h + 1 To upBound  
            v = t(i): j = i  
            Do While t(j - h) > v  
                t(j) = t(j - h): j = j - h  
                If j <= h Then  
                    Exit Do  
                End If  
            Loop  
            t(j) = v  
        Next i  
    Loop Until h = loBound  
End Sub

Le Tri rapide (Quick Sort)

Le Tri Rapide est un tri basé sur la méthode "diviser pour régner" ("divide and conquer"). Cette méthode a été inventée par C.A.R. Hoare en 1962. Elle utilise une méthode récursive. Son principe est de diviser le tableau en sous tableaux pour ne plus avoir finalement qu'à trier des petits tableaux de 2 éléments. Cette méthode est assez compliquée à comprendre et à implémenter proprement, mais elle est très efficace, bien adaptée au tri de tableaux comportant beaucoup d'éléments (N grand). Ce tri est aussi particulièrement bien adapté pour trier des tableaux très désordonnés. En pratique, il est aussi efficace que le tri de Shell. A noter que dans des conditions très particulières, il peut dégénérer et s'avérer alors très peu performants.

'  
' Tri Rapide - Quick Sort  
' Based on original code : http://www.vb-helper.com/howto_quicksort.html   
'
Public Sub Quicksort(t() As Long, _  
                    ByVal loBound As Long, _  
                    ByVal upBound As Long)  
                      
    Dim med_value As Long  
    Dim hi As Long  
    Dim lo As Long  
    Dim i As Long  

    If loBound >= upBound Then Exit Sub  
    i = Int((upBound - loBound + 1) * Rnd + loBound)  
    med_value = t(i)  
    t(i) = t(loBound)  
    lo = loBound  
    hi = upBound  
    Do  
        Do While t(hi) >= med_value  
            hi = hi - 1  
            If hi <= lo Then Exit Do  
        Loop  
        If hi <= lo Then  
            t(lo) = med_value  
            Exit Do  
        End If  
        t(lo) = t(hi)  
        lo = lo + 1  
        Do While t(lo) < med_value  
            lo = lo + 1  
            If lo >= hi Then Exit Do  
        Loop  
        If lo >= hi Then  
            lo = hi  
            t(hi) = med_value  
            Exit Do  
        End If  
        t(hi) = t(lo)  
    Loop  
    ' Recursive calls  
    Quicksort t(), loBound, lo - 1  
    Quicksort t(), lo + 1, upBound  
End Sub  

Les langages de programmation qui fournissent des fonctions de tris dans leur librairie standard emploient l'une ou l'autre de ces 2 dernières méthodes. Par exemple, Ocaml utilise Shell Sort, C en général QuickSort.

Arbre binaire de recherche (Binary Search Tree)

Il ne s'agit pas à proprement parler d'une méthode de tri. L'idée est de fabriquer un arbre binaire de recherche ("Binary Search Tree") et d'exploiter l'une de ses propriétés intéressantes : le parcours infixe d'un tel arbre permet de restituer les éléments dans l'ordre.
Le principe de construction est très simple : on insère le premier élément, qui devient la racine, puis pour chaque nouvel élément, on insère à gauche si il est plus petit et à droite si il est plus grand. Comme il s'agit d'un arbre binaire, chaque noeud ne peut avoir que 2 fils (un gauche, un droite). Voici la construction d'un tel arbre, dans lequel on veut insérer les valeurs 6, 8, 3, 1, 4, 9, 2, 7 et 5 :

  • On insère 6 à la racine
  • 8 > 6, on insère à droite
  • 3 < 6, on insère à gauche
  • 1 < 6, on insère à gauche, 1 < 3, on insère à gauche de 3
  • 4 > 6, on insère à gauche, 4 > 3, on insère à droite de 3
  • 9 > 6, on insère à droite, 9 > 8, on insère à droite de 8
  • etc.
Et en voici la représentation graphique :
Arbre binaire

La construction d'un tel arbre est très simple (grâce aux appels récursifs). Voici l'implémentation en pseudo-code :

' Pseudo-code !
Sub AddNode(NewNode as Node, CurNode as Node)

    If NewNode.Value > CurNode.Value Then  
        ' Add to right  
        If CurNode.Right <> Nothing Then  
            AddNode(NewNode, CurNode.Right)  
        Else  
            Set CurNode.Right = NewNode  
        End If  
    Else  
        ' Add to Left  
        If CurNode.Left <> Nothing Then  
            AddNode(NewNode, CurNode.Left)  
        Else  
            Set CurNode.Left = NewNode  
        End If  
    Endif  

End Sub

Pour le tri, il suffit d'effectuer un parcours infixe de l'arbre. Le parcours infixe consiste à visiter récursivement le sous arbre gauche de l'arbre puis de concaténer le noeud de l'arbre avant de visiter le sous arbre droit. La formulation parait compliquée mais c'est en réalité très simple, comme le montre le pseudo-code suivant :

Sub ParcoursInfixe(N as Node)
    If N = Nothing Then
        ' nothing to do, then Return
    Else
        ParcoursInfixe(N.Fils_Gauche)
        Write Node.Value
        ParcoursInfixe(N.Fils_Droit)
    End If
End Sub

Cette structure de données est bien adaptée pour le rangement et la recherche d'éléments pour un grand volume de données. Les performances de cette méthode sont comparables à celles du tri rapide. A noter cependant que dans le cas le plus défavorable (éléments triés à l'envers), cette méthode devient mauvaise, car l'arbre devient "dégénéré" (arbre filiforme). Quand on utilise ce type de structure, une pratique courante est de mélanger les données avant de construire l'arbre, justement pour éviter les cas limites; Le désordre apporté aura au final un impact positif sur la structure de l'arbre! Ces méthodes sont classiques mais leur description dépasse le cadre de cet article; La section "Aller plus loin" présente des liens sur le sujet.

Méthodes alternatives

Utilisation de SQL

Pour des tris plus complexes, par exemple des tris multicritères, les méthodes classiques ne sont pas forcément le meilleur choix. On peut recourir pour ces cas à l'utilisation d'une base de données. Il est très simple de remplir une table avec les données, de les trier avec le traitement SQL approprié, et de récupérer le résultat trié. Dans de nombreux cas, cette méthode se révélera très performante et constituera le meilleur choix, tant en terme de vitesse qu'en terme de souplesse et de simplicité de programmation. Le prix à payer est l'ajout d'une référence à une base de données ainsi que l'obligation de charger les données en base, de trier, puis enfin de recharger les données de la base vers la structure en mémoire. Ce prix est acceptable en général, en comparaison de la difficulté de l'implémentation vraiment efficace de tris multicritères ou sur des types de données hétérogènes.

Exemple : Tri de livres. Pour chaque ouvrage, on a "Auteur", "Titre", "Genre". On désire trier les enregistrements selon ces critères, dans l'ordre Genre, Auteur, Titre. Avec les méthodes classiques, il va falloir modifier l'un des algorithmes, et implémenter une nouvelle fonction de comparaison. De plus, pour chaque nouveau cas (tri avec d'autres critères), il va falloir implémenter une nouvelle fonction. Avec une base de donnée et l'utilisation de SQL, le tri est trivial :

Private Sub Tri_DB()

    Dim dbName As String
    Dim db As Database, rs As Recordset
    Dim sqlQuery As String

    dbName = "biblio.mdb"
    Set db = OpenDatabase(dbName)
     
    sqlQuery = "SELECT * FROM Touvrages ORDER BY Genre, Auteur, Titre"
     
    Set rs = db.OpenRecordset(sqlQuery)
    ' suite
End Sub

Bien sur, il est très facile de générer dynamiquement la requête SQL en fonction des choix de l'utilisateur, par exemple.

Utilisation du contrôle VB "Listbox"

Nous ne mentionnons cette méthode qu'à titre anecdotique car ce n'est pas une bonne façon de procéder. On peut créer sur une forme une Listbox invisible, avec la propriété Sorted égale à True; Ceci à pour effet de maintenir la liste triée au fur et à mesure des ajouts. Il suffit alors d'ajouter les éléments à trier dans n'importe quel ordre, par des appels successifs à Additem. Puis, on relit simplement les éléments de la ListBox du premier au dernier. Attention : ceci n'est valable que pour des chaînes de caractères car le tri effectué est un tri lexicographique, en aucun cas numérique. Cette méthode a des inconvénients : elle est très peu efficace et elle est limitée par le nombre d'éléments que peut contenir une listbox (environ 32000). Mais son plus grand inconvénient est sans nul doute le fait que son utilisation rend difficile la séparation "Code/Interface". Cependant, elle est particulièrement simple à mettre en oeuvre par les débutants.

Pour aller plus loin

Comme il a été dit au début, cet article n'a pas vocation à présenter toutes les méthodes de tri, ni à donner une explication détaillée de toutes ces méthodes. Ceci dépasserait (et de beaucoup!) le cadre de ce simple article. La quantité de littérature sur le sujet étant immense, il est aisé de trouver en ligne de nombreux articles, cours et tutoriaux sur le sujet.

La liste suivante présente quelques liens intéressants, aussi bien de ressources en ligne que hors-ligne (livres, etc.) :

Voir aussi :

Date de publication : 25 février 2007
Dernière modification : 13 septembre 2007
Rubriques : Algorithmique
Mots-clés : algorithme, algorithmes, tri, tris, sort, trier, données, data, quicksort, tri rapide, tri shell, shellsort, tri à bulle, bubblesort, bulle, arbre binaire, arbres binaire, binary tree, arbre, récursif, récursivité, divide and conquer, diviser pour régner, complexité, ranger, ordonner, SQL, requêtes, tri base de données