Le tri le plus rapide

Soyez le premier à donner votre avis sur cette source.

Vue 18 830 fois - Téléchargée 1 095 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.

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

Ajouter un commentaire Commentaires
Messages postés
9
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
2 novembre 2008

Y a pas à dire .... c'est hyper rapide.
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.
Messages postés
77
Date d'inscription
samedi 28 décembre 2002
Statut
Membre
Dernière intervention
20 juillet 2005

Je n'ai qu'un mot BRAVO

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 !
Messages postés
9
Date d'inscription
mardi 24 décembre 2002
Statut
Membre
Dernière intervention
27 février 2008

Une listview cacher "trier" c'est fait !!!!! beaucoup plus rapide
Messages postés
12
Date d'inscription
mercredi 24 décembre 2003
Statut
Membre
Dernière intervention
1 novembre 2004

D'après mes souvenirs de programmation en Pascal, une méthodes de tri par arbre binaire dépassait et de très loin toutes les méthodes de tri.
Il suffisait de chainer les éléments à trier et de les orienter à droite ou à gauche, suivant l'ordre en construisant un arbre.
Messages postés
4
Date d'inscription
mercredi 9 avril 2003
Statut
Membre
Dernière intervention
20 mai 2003

Ben oui ! Tu n'as rien inventé ...
Quicksort = The best !
Afficher les 12 commentaires

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.