Discussion :

[logue_in]

Bonjour,

J'aimerais trier par ordre de grandeur la 1er colonne d'une listbox mais tout en gardant la correspondance sur la colonne 2.
J'ai trouvé ce code sur le forum. Quelqu'un peut-il m'expliquer le pas à pas. Je ne comprends pas le sub tri(a)...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Private Sub LCP_Click()
    Dim a()
    a = Me.ListBox1.List
    NbCol = UBound(a, 2) - LBound(a, 2) + 1
    Call tri(a(), LBound(a), UBound(a), NbCol, 2)
    Me.ListBox1.List = a
End Sub
 
Sub tri(a(), gauc, droi, NbCol, colTri) ' Quick sort
   ref = a((gauc + droi) \ 2, colTri)
   g = gauc: d = droi
   Do
     Do While a(g, colTri) < ref: g = g + 1: Loop
     Do While ref < a(d, colTri): d = d - 1: Loop
       If g <= d Then
          For c = 0 To NbCol - 1
             temp = a(g, c): a(g, c) = a(d, c): a(d, c) = temp
          Next
          g = g + 1: d = d - 1
       End If
   Loop While g <= d
   If g < droi Then Call tri(a, g, droi, NbCol, colTri)
   If gauc < d Then Call tri(a, gauc, d, NbCol, colTri)
End Sub

[logue_in]

bo, j'étais passé à coté de ça:
http://www.developpez.net/forums/d12...ions-code-vba/

Mais je ne comprend pas:

Ref = A((Gauche + Droite) \ 2, ColTri)
G = Gauche
D = Droite

[Philippe PONS]

Ben comme indiqué dans le lien, quicksort fait un tri dichotomique.
C'est à dire que l'algorithme coupe le tableau en 2 parties et regarde
si la valeur cherchée est à droite ou à gauche de la moitié du tableau.
Donc (Gauche + Droite) \ 2 calcul l'index de la moitié du tableau.
tri est une procédure récursive: elle s'appelle elle-même, ici

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
If g < droi Then Call tri(a, g, droi, NbCol, colTri)
If gauc < d Then Call tri(a, gauc, d, NbCol, colTri)

HTH,

[boisgontierjacques]

Bonjour,


Le principe du tri Quick-sort 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éjà 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.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Sub TriQuick()
  n = 10000          ' 0,04 sec
  Dim temp() As Double
  ReDim temp(1 To n)
  For i = 1 To n:  temp(i) = Rnd:  Next i
  Call tri(temp, 1, n)
  [A1].Resize(n) = Application.Transpose(temp)
End Sub

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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

Boisgontier