Hit-Parade .VB Research Center . Compteur
Accueil ~  Code ~  Programmes ~  Api ~  Forum ~  Cours ~  Livres ~  Quiz ~  Annuaire
~ Edito ~
12/03/2006 @ 13:39
Depuis la dernière mise à jour (qui remonte à... oulala plusieurs mois), un petit ménage de printemps s'impose. Ca tombe bien, c'est presque la période.
Au menu, et progressivement sur les jours à venir, rafraîchissement de plusieurs fonctions et procédures, nouvelles APIs et nouveaux programmes.

~ Rechercher ~

  

~ Annuaire VB ~
 Rechercher un site :
  

~ Partenaires ~

Divers : Fonctions de Tri
Trois fonctions de tri expliquées avec leur code.
(Consulté 22040 fois.)

Les fonctions de tri sont des éléments du code très sensible. Elles doivent être rapides et efficaces. On doit pouvoir aussi les adapter facilement à tout type de tableau de données. Et il peut être également important de comprendre leur fonctionnement, histoire de pas avoir l'air trop bête quand quelqu'un vous demande : "Eeeeh, elle est super ta fonction, mais comment elle marche?"
Sur cette page seront abordées trois fonctions de tri. Allant du plus simple et moins rapide, au moins facile à comprendre mais plus rapide!

  • 1 - Le tri à bulle

Ce tri est le premier que l'on apprend à faire (et à ne plus faire...). Il est très facile à comprendre, mais sa lenteur, à partir d'un certain nombre d'élément est désespérante! Comme son nom l'indique, on va faire remonter les éléments les plus petits (ou les plus grand suivant l'ordre dans lequel vous désirez trier) en bout de liste. Comme une bulle d'air qui remonte à la surface...
Le principe est donc le suivant :
- On parcourt tous les éléments en partant du début et allant vers la fin (ou l'inverse, comme cela est fait dans la fonction donnée ci-dessous).
- On regarde si notre élément courant est plus grand (ou plus petit...) que tous les autres éléments qui le suivent.
- Si on rencontre un élément qui devrait être devant lui, on échange alors leurs place.
- Au bout du premier tour, on a ramener donc, le plus grand élément en début de liste (ou le plus petit).
- On reparcourt donc la liste en partant du second élément (puisque maintenant on ne trouvera pas plus grand que le premier).

  • 2 - Le tri par recherche du maximum

Ce tri reprend d'une certaine manière le principe du premier. Mais il optimise en fait les échanges de position. Au lieu de faire remonter un élément en le changeant de place à chaque fois, on enregistre ici la position de l'élément qui prendra sa place, puis après avoir parcouru tout le tableau et enregistré la position du plus grand (petit) élément, on peut faire l'échange.
Voici en résumé le principe :
- On va parcourir un par un tous les éléments du tableau.
- On enregistre la position de l'élément courant.
- On parcourt cette fois-ci complètement le tableau, en comparant chacun des éléments avec celui dont on a enregistré la position.
- Si on rencontre un élément plus grand (ou plut petit suivant votre choix) que celui enregistré, on enregistre alors sa position à la place de celui qu'on avait en mémoire.
- Lorsque le tableau est fini d'être parcouru, on prend l'élément dont on a vu qu'il était le plus grand (petit), et on le change de place avec d'où on était parti.

Remarque : On pourrait mettre un test à la fin pour voir si lgTmp est effectivement différent de lgMin... Cela peut se discuter, il faut voir si le tableau est vraiment bien mélangé ou pas. Il est certain qu'un test coute moins cher qu'un échange de place!

  • 3 - Le tri par sélection

Je ne sais plus si le nom pour ce tri est correct. Toujours est-il que, quand il a fallu que je remette le nez dans ces quelques lignes, cela m'a pris une bonne demi-heure pour me souvenir du principe de fonctionnement. Je vais essayer de vous réduire ce temps de réflexion en vous donnant quelques explications. Je ne saurais que trop vous conseiller de vous enfermer au calme pendant quelques minutes avec VB en mode debug en prenant un exemple simple et en regardant comment cela fonctionne. Rien ne vaut un bon exemple!!
Je suis parti sur le tableau de 10 éléments suivant :
8 - 9 - 10 - 5 - 6 - 7 - 2 - 3 - 4 - 1
Cette méthode se positionne approximativement à partir du premier tiers du tableau, puis va jusqu'à la fin en comparant au fur et à mesure l'élément courant avec un autre élément issu d'un calcul basé sur la position actuelle et le premier élément.
Dans mon cas, l'élément en position 5 (mon élément dit courant, en rouge) est comparé avec celui en position 1 (mon élément dit de comparaison, en bleu).
8 - 9 - 10 - 5 - 6 - 7 - 2 - 3 - 4 - 1
Après on comparera :
8 -
9 - 10 - 5 - 6 - 7 - 2 - 3 - 4 - 1
Puis :
8 - 9 -
10 - 5 - 6 - 7 - 2 - 3 - 4 - 1
Et ainsi de suite jusqu'à la fin.
Lorsque mon élément courant est plus petit que mon élément de comparaison, on remplace la valeur de mon élément courant par celle de l'élément de comparaison. Ainsi, après le 4ième tour on aura un tableau dans ce genre (les trois premières comparaisons ont donné lieu à des échanges) :
6 - 7 - 2 - 3 -
8 - 9 - 10 - 5 - 4 - 1
La apparaît la dernière subtilité de ce tri (le reste, c'est ensuite toujours la même chose!). Ici, on compare donc le 4 avec le 8. Le test remplace donc la valeur de notre élément courant (pas d'inquiétude, la valeur de notre élément courant est conservé en mémoire) :
6 - 7 - 2 - 3 -
8 - 9 - 10 - 5 - 8 - 1
Il s'avère que l'élément de comparaison (en bleu), se trouve exactement à la place ou se trouvait notre élément courant au début de la boucle (voir première ligne avec le 6 en rouge). On compare donc maintenant notre valeur en mémoire avec le second élément de comparaison, ce qui fait qu'après le test on obtient la ligne suivante :
4 - 7 - 2 - 3 - 6 - 9 - 10 - 5 - 8 - 1
On a donc fait une sorte de rotation entre le 4, le 8 et le 6.
On pourrait voir ce tri comme un tri à bulle plus performant, en effet, au lieu d'échanger des valeurs qui se trouvent côte à côte, on le fait sur un intervalle plus important. Bref, les explications ne sont pas forcément faciles à comprendre, en suivant le code pas à pas, on se rend mieux compte. Vous pouvez donc vous appuyer sur ces quelques lignes comme point de départ, le reste viendra tout seul ensuite.
Ce code est bien entendu le plus rapide des trois.

Public Sub TriABulle(tabLong() As Long)
Dim
lgFor1 As Long, lgFor2 As Long
Dim
lgTmp As Long, lgMin As Long
lgMin = LBound(tabLong)
' Parcourt l'ensemble des éléments du tableau
For lgFor1 = UBound(tabLong) To lgMin Step -1
' Parcourt l'ensemble des éléments non triés du tableau
    For lgFor2 = lgMin + 1 To lgFor1
       
If tabLong(lgFor2 - 1) > tabLong(lgFor2) Then
' Echange de place entre deux éléments
            lgTmp = tabLong(lgFor2 - 1)
            tabLong(lgFor2 - 1) = tabLong(lgFor2)
            tabLong(lgFor2) = lgTmp
       
End If
    Next lgFor2
Next lgFor1
End Sub

Public Sub
TriParRechMax(tabLong() As Long)
Dim
lgFor1 As Long, lgFor2 As Long
Dim
lgMin As Long, lgTmp As Long
For
lgFor1 = LBound(tabLong) To UBound(tabLong) - 1
' Position de l'élément courant (supposé le plus petit)
    lgMin = lgFor1
   
For lgFor2 = lgFor1 + 1 To UBound(tabLong)
' Si on rencontre plus petit que celui en mémoire, on enregistre alors sa position
        If tabLong(lgFor2) < tabLong(lgMin) Then lgMin = lgFor2
   
Next lgFor2
' Change les éléments de position
    lgTmp = tabLong(lgMin)
    tabLong(lgMin) = tabLong(lgFor1)
    tabLong(lgFor1) = lgTmp
Next lgFor1
End Sub

Public Sub
TriParSelection(tabLong() As Long)
Dim
lgFor As Long
Dim
lgMem As Long, lgTiers As Long
Dim
lgTmp As Long
lgTiers = LBound(tabLong)
Do
    lgTiers = 3 * lgTiers + 1
Loop Until lgTiers > UBound(tabLong)
Do
    lgTiers = lgTiers / 3
   
For lgFor = lgTiers + LBound(tabLong) To UBound(tabLong)
' Enregistrement de la valeur de l'élément "courant"
        lgTmp = tabLong(lgFor)
        lgMem = lgFor
       
Do While tabLong(lgMem - lgTiers) > lgTmp
' Ecrase la valeur de l'élément "courant" (ou de comparaison, à partir du second tour)
            tabLong(lgMem) = tabLong(lgMem - lgTiers)
' Recherche la position d'un nouvel élément de "comparaison"
            lgMem = lgMem - lgTiers
' Evite de sortir des limites du tableau
            If lgMem < lgTiers Then Exit Do
        Loop
' Enregistre la valeur de l'élément courant à la place de
' l'élément de comparaison si l'échange a effectivement eu lieu.
' Sinon, cela n'a aucun effet, enregistrement de l'élément courant
' sur lui-même
        tabLong(lgMem) = lgTmp
   
Next lgFor
Loop Until lgTiers = LBound(tabLong)
End Sub

Visual Basic Research Center - (c) 2000/2002 -  Webmaster : docvb (chez) free (point) fr