Soyez le premier à donner votre avis sur cette source.
Vue 19 070 fois - Téléchargée 1 111 fois
Public Compteur As Long 'Taille du tableau Public Words(0 To 100000) As String ' Tableau Principal (à trier) Public a(0 To 100000) As String 'Tableau Tampon (utilisé par la fonction Réorganise()) 'Fonction qui génère aléatoirement des tableaux pour tester 'la vitesse de ma fonction de tri Sub Génère(n As Long) Compteur = n Dim Texte$ For x = 0 To n Texte$ = "" For Y = 0 To 5 + Int(Rnd * 10) Texte$ = Texte$ + Chr$(Int(Rnd * 26) + 65) Next Words(x) = Texte$ Next End Sub 'TriBulle: cette méthode est lente pour des tableaux très longs 'il serait honteux de commenter une telle fonction Sub TriBulle(Début As Long, Fin As Long) For x = Début To Fin - 1 For Y = Fin To x Step -1 If Words(x) > Words(Y) Then w = Words(x): Words(x) = Words(Y): Words(Y) = w Next Next End Sub ' MA Fonction de tri (récurente) cf commentaires tout en bas! Sub tri(Début As Long, Fin As Long) Dim Moitié As Long Moitié = (Début + Fin) / 2 If Fin - Début > 10 Then 'SI le tableauestt de Dimension <10 Call tri(Début, Moitié) 'ALORS : on rappelle récursivement Tri() sur la 1° moitié Call tri(Moitié + 1, Fin) ' on rappelle récursivement Tri() sur la 1° moitié Call Réorganise(Début, Fin) ' on fusionne les deux sous-tableaux Else 'SINON : Call TriBulle(Début, Fin) ' on tri le tableau à l'aide de TriBulle End If '*******ET VOILA!!!******* End Sub ' <|:0) 'Cette fonction sert à réorganiser les sous-tableaux Triés Sub Réorganise(Début As Long, Fin As Long) Dim Moitié As Long 'Sous-tableau 1 : (début To moitié) 'sous-tableau 2 : (moitié+1 To fin) Moitié = (Début + Fin) / 2 For x = Début To Fin 'passage du tableau principal dans le tableau a(x) = Words(x) 'tampon Next ' x = Début z = Début Y = Moitié + 1 While x <= Moitié And Y <= Fin 'Comparaison des deux sous tableaux If a(x) > a(Y) Then 'Le tableau principal est rempli Words(z) = a(Y) 'jusqu'à-ce qu'il y ai un sous tableau Y = Y + 1 'parcouru entièrement Else ' Words(z) = a(x) ' x = x + 1 ' End If ' z = z + 1 ' Wend ' ' à partir de là, on complète le tableau principal avec les éléments contenus ' dans le sous-tableau qui n'a pas été parcouru entièrement If x <= Moitié Then While x <= Moitié Words(z) = a(x) z = z + 1 x = x + 1 Wend Else While x <= Moitié Words(z) = a(Y) z = z + 1 Y = Y + 1 Wend End If End Sub ' Cette fonction de Fusion est la même que la fonction Réorganise() ' mais elle n'utilise pas de tableau supplémentaire, en revanche elle 'est plus lente Sub Fusion(Début As Long, Fin As Long) Dim Moitié As Long Dim Y As Long Dim Char As String Moitié = (Fin + Début) / 2 Y = Début For x = Moitié + 1 To Fin While Y < x And Words(Y) <= Words(x) Y = Y + 1 Wend If Y = x Then Exit For Char = Words(x) For c = x To Y + 1 Step -1 Words(c) = Words(c - 1) Next Words(Début + Y) = Char Y = Y + 1 Next End Sub '*----------------------------------------------------------------------* '| Détail de l'agorithme de Tri | '*----------------------------------------------------------------------* ' La fonction Tri() (ou plutôt Sub) prend en paramètres le début du tableau 'à trier et la fin de ce tableau. ' 'L'algorithme de tri consiste à diviser le tableau en sous tableaux de 'taille 10 ou 11 (selon que le nombre d'entrée du tableau,i.e. `Compteur`, 'est pair ou impair). Ensuite il applique le TriBulle à chaque sous-tableau 'et fini par les fusioner tous grâce à la fonction Réorganise() ou Fusion() 'au choix(de l'utilisateur). Cette fonction réorganise les sous tableaux '2 par 2. ' ' 'Petit exemple mais en prenant des sous-tableaux de taile 2 avec un tableau de 'taille 10: 'ST1-1: ' 1 : gdhf | |1 : bedf | |ST2-1 : |ST3-1 : |Tableau final : ' 2 : bedf | |2 : gdhf | |1 : bedf |1 : bedf |1 : bedf 'ST1-2 : | |ST1-2 : | |2 : dksi |2 : dksi |2 : dksi ' 3 : kild | |3 : dksi | |3 : gdhf |3 : gdhf |3 : gdhf ' 4 : dksi |Tri de |4 : kild |Réorganisation|4 : kild |4 : gdys |4 : gdys 'ST1-3 : |chaque |ST1-3 : |du tableau |ST2-2 : |5 : kild |5 : kild ' 5 : gdys |sous- |5 : gdys |avec |5 : gdys |6 : lsop |6 : lsop ' 6 : uitp |tableau |6 : uitp | |6 : lsop |7 : mopl |7 : mopl 'ST1-4 : |par la |ST1-4 : |Réorganise() |7 : mopl |8 : uitp |8 : nbig ' 7 : lsop |fonction |7 : lsop | |8 : uitp |ST3-2 : |9 : nhiu ' 8 : mopl |TriBulle |8 : mopl |Fusion() ne |ST2-3 : |9 : nbig |10: uitp 'ST1-5 : | |ST1-5 : |fonctionne pas|9 : nbig |10 : nhiu | ' 9 : nhiu | |9 : nbig |pareil. à vous|10: nhiu | '10 : nbig | |10: nhiu |de trouver | 'La fonction Tri n'est pas très compliqué. Elle est même simple pour peu que 'l'on connaisse la récursivité. ' Par AGAGA <|;0)
2 juin 2005 à 13:51
Je l'utilise pour trier des tableaux de chaînes de caractères de 100 000 lignes
Ca mérite bien un 10 sur 10 pour l'efficacité et la simplicité du code.
10 févr. 2004 à 15:19
L'algo est sans bug, compréhensible, très rapide et j'ai put l'adapter facilement a mes tableaux à deux dimensions, faire des tris décroissants.
Ca mérite un 10/10 !
9 janv. 2004 à 15:31
26 déc. 2003 à 00:24
Il suffisait de chainer les éléments à trier et de les orienter à droite ou à gauche, suivant l'ordre en construisant un arbre.
19 mai 2003 à 12:01
Quicksort = The best !
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.