Le tri le plus rapide

Télécharger le projet
Commenter

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 :)!
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_Agaga)