Le principe est le suivant:
On répartit la suite de nombres à trier de telle sorte que tous les éléments inférieurs à un élément de référence (36 sur l'exemple) soient à gauche de celui-ci et que tous ceux qui lui sont supérieurs à sa droite.
[70 61 16 48 29 18 59 36 3 70 3 22 39 30 58 10] <- Avant
¦
Elément
médian de référence
¦
[3 30 16 22 29 18] 36 [70 59 48 39 59 61 58 70] <- Après
¦
¦
Eléments<36 Eléments>36
Tous les éléments de l'ensemble de droite sont supérieurs à ceux de l'ensemble de gauche. En procédant de la même façon sur les 2 sous-ensembles générés,on obtient 4 sous-ensembles ordonnés entre eux. Lorsque la taille des ensembles devient égale à 1,les nombres sont triés.
Choix de l'élément de référence:
Pour obtenir des sous-ensembles de tailles équilibrées,il faut que l'élément de référence ne soit ni trop petit,ni trop grand.
La méthode classique consiste à choisir l'élément
de référence parmi 3 éléments:Ceux de gauche,du
milieu et de droite.
Nous observons qu'en choisissant l'élément de référence
au milieu de la liste à traiter, le temps de tri est le même.
Remarques:
-Si la liste est déja triée,le temps de tri n'augmente pas lorsque
l'élément de référence est choisi au milieu,ce qui
n'est pas le cas lorsqu'il est choisi à gauche.
-Le programme proposé est récursif.
Sub essai()
Dim temp(10000) As Double
For i = 1 To 10000
temp(i) = Rnd
Next i
t = Timer
Call tri(temp, 1, 10000)
MsgBox Timer - t
End Sub
Sub tri(a() As Double, gauc, droi) ' Quick sort
ref = a((gauc + droi) \ 2)
g = gauc: d = droi
Do
Do While a(g) < ref: g = g + 1: Loop
Do While ref < a(d): d = d - 1: Loop
If g <= d Then
temp = a(g):
a(g) = a(d): a(d) = temp
g = g + 1:
d = d - 1
End If
Loop While g <= d
If g < droi Then Call tri(a, g, droi)
If gauc < d Then Call tri(a, gauc, d)
End Sub