Comment trier des données en VB ? Quelles sont les différentes méthodes de tri ?
IntroductionTrier 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émentationsDans 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.
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.
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).
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
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
If t(i) > t(i + 1) Then
test = i
tmp = t(i)
t(i) = t(i + 1)
t(i + 1) = tmp
End If
Next i
k = test
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!).
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.
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
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 :
 La construction d'un tel arbre est très simple (grâce aux appels récursifs). Voici l'implémentation en pseudo-code :
Sub AddNode(NewNode as Node, CurNode as Node)
If NewNode.Value > CurNode.Value Then
If CurNode.Right <> Nothing Then
AddNode(NewNode, CurNode.Right)
Else
Set CurNode.Right = NewNode
End If
Else
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
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 alternativesUtilisation de SQLPour 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)
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 loinComme 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 : |
Top