'***************************************************************************************************************************
'**********************************************************************************
' __ _____ ___ . ___ _____ ___ ___
'|__| /\ | | | | | | / | | | | | | | | |\ |
'| /__\ | |--- | | |/\ | | | | | | | | | \ |
'| / \ | | \ | |___ | \ | |___| |___| |__ |___| | \|
'
'***********************************************************************************
'RECEUIL DE M2THODE DE TRI D UN ARRAY
'Methode 3
' Tri rapide (quick sort)
'Le tri rapide (quicksort), ou tri pivot, fait aussi partie de la famille des algorithmes « diviser pour régner ».
'Lui aussi utilise donc de la récursivité et sa logique est un peu plus complexe. '
'Comme le tri fusion, il est cependant grandement utilisé dans les langages modernes.
'Son fonctionnement est centré autour du concept du pivot.
'On va choisir un élément dans le tableau et on va décréter que cet élément est le pivot pour une itération sur le tableau.
'Y’a différente façon de choisir un pivot, on ne va pas rentrer là-dedans, '
'aujourd’hui le pivot sera l' élément du milieu du tableau.
'Une fois qu’on a ce pivot, on va faire 2 boucles du debut au milieu et du milieu à droite
'Toutes les valeurs plus basses que ce pivot vont à gauche de ce tableau.
'Toutes les valeurs plus grandes que ce pivot vont à droite.
'donc en sortie de ces deux sub boucles la plus petite valeur droite et la plus petite valeur gauche
'sont interverties si celle de droite est plus petite
'Et ensuite on va appeler de façon récursive La même fonction avec les argument tableau et D et G et gauche et droite
'les appels récursifs s 'arretent dès que G est plus petit que Droite et que gauche est plus petit que D
'grossomodo un apel récursif est en moyenne 10% plus rapide que une incrementation dans une boucle
'ce qui fait de cette méthode une des plus rapide
Dim Q&, Ch&
Sub Test_a_Grande_Echelle_QUICKSORT()
Q = 0: Ch = 0: tim = Timer
Cells(1, 3).Resize(10000).ClearContents
t = Application.Transpose(Cells(1, 1).Resize(10000).Value)
t = SortQuickSort(t, xlDescending) 'ou XlAscending
MsgBox Format(Timer - tim, "#0.00") & " sec" & vbCrLf & Q & " TOURS DE BOUCLE SUR 3 DO/LOOP" & vbCrLf & Ch & " INTERVERTIONS"
Cells(1, 3).Resize(10000) = Application.Transpose(t)
End Sub
Function SortQuickSort(tbl, Optional Sortmode As Long = 1, Optional Gauche = -1, Optional Droite = -1) ' Quick sort
Dim ref, G&, D&, temp1, First, tim#
If Droite = -1 And Gauche = -1 Then First = 1 Else First = 0
Droite = IIf(Droite = -1, UBound(tbl), Droite)
Gauche = IIf(Gauche = -1, LBound(tbl), Gauche)
ref = tbl((Gauche + Droite) \ 2) 'le pivot( change de position au fur et a mesure)
G = Gauche: D = Droite 'on dédouble les variable gauche et droite pour l'incrémentation dans les deux do/loop droite et gauche
Do
If Sortmode = 1 Then
Do While tbl(G) < ref: G = G + 1:: Loop 'on comptabilise le passage
Do While ref < tbl(D): D = D - 1: Q = Q + 1:: Loop 'on comptabilise le passage
Else
Do While tbl(G) > ref: G = G + 1:: Loop 'on comptabilise le passage
Do While ref > tbl(D): D = D - 1: Q = Q + 1:: Loop 'on comptabilise le passage
End If
'intervertion des itemS tbl(G) à gauche du pivot et l'item tbl(d) à droite du pivot
If G <= D Then
temp1 = tbl(G): tbl(G) = tbl(D): tbl(D) = temp1
G = G + 1: D = D - 1
Ch = Ch + 1
End If
Loop While G <= D
'si g ou gauche est plus petit on relance un appel de la fonction (c'est la récursivité)
If G < Droite Then x = SortQuickSort(tbl, Sortmode, G, Droite)
If Gauche < D Then x = SortQuickSort(tbl, Sortmode, Gauche, D)
'pour économiser un peu la charge memoire du return de la fonction on la charge dès que l'on revients à first
'c'est à dire quand il n'y a plus d'appel récursifs
If First = 1 Then SortQuickSort = tbl
End Function
