Le tri le plus rapide
Soyez le premier à donner votre avis sur cette source.
Vue 19 070 fois - Téléchargée 1 111 fois
Description
Voici un algorithme de tri, apremière vue compliqué, mais EXTREMEMENT RAPIDE. A vrai dire je n'ai encore trouvé aucun algorithme de tri aussi rapide! Et IL EST DE MOI!!!!! <|:0)
Ci-dessous le module de tri mais il y a aussi un zip si vous voulez avoir une form prévue pour une démo.
c'est récursif, c'est mortel et j'en suis fier!
Vos commentaires sont toujours les bienvenus :)!
Ci-dessous le module de tri mais il y a aussi un zip si vous voulez avoir une form prévue pour une démo.
Source / Exemple :
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)
Conclusion :
c'est récursif, c'est mortel et j'en suis fier!
Vos commentaires sont toujours les bienvenus :)!
Codes Sources
A voir également
- Tri fusion ocaml
- Tri fusion caml - Meilleures réponses
- Algorithme de tri le plus rapide - Meilleures réponses
- Tri fusion c++ vector ✓ - Forum - C++ & C++ .NET
- Tri fusion java - Guide
- Tri fusion itératif - Forum - C / C++ / C++.NET
- PHP : Tri fusion - mergesort - CodeS SourceS - Guide
- Complexité de l'algorithme de Tri Fusion ✓ - Forum - C
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.