Fonction performante de tri de tableaux

Publié le par

Il existe plusieurs dizaines de méthodes de tri de tableaux et la plus renommée est Quicksort en terme de rapidité.
Qu’en est-il en VBA ?

J’ai testé plusieurs algorithmes dont Insertionsort, Heapsort, Mergesort, Quicksort, mais mon préféré reste Shellsort par sa compacité, simplicité et sa rapidité. L’efficacité de Shellsort réside dans le choix des gaps qui ont fait l’objet de multiples publications depuis les années 60. Les meilleurs gaps semblent bien définis jusqu’à la valeur de 1750.

Ma fonction Shellsort

'Shellsort - Philben - v1.0 - 03/2012
'Utilisable pour des tailles de tableau jusqu'à 10 000 000
'La valeur des gaps au-dessus de 1750 sont extrapolées et ne sont certainement pas les plus efficaces !
'Si le type de tableau est Integer, modifier :
'  - ByRef a() As Long  en ByRef a() As Integer
'  - Dim ref As Long    en Dim ref As Integer
Public Function ShellSort(ByRef a() As Long, ByVal lowerBound As Long, ByVal upperBound As Long)
   Dim ref As Long
   Dim h As Long, i As Long, j As Long, k As Long, l As Long, m As Long, n As Long, g As Variant
 
   g = Array(1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 10941, 27353, 68383, 170958, 427396, 1068491, 2671228)
   n = upperBound - lowerBound + 1
 
   l = LBound(g)
   If n < g(UBound(g)) Then
      k = l
      While g(k + 1) < n: k = k + 1: Wend
   Else
      k = UBound(g)
   End If
 
   While k >= l
      h = g(k)
      m = lowerBound + h
      For i = m To upperBound
         ref = a(i)
         j = i
         Do While ref < a(j - h) '< pour un tri croissant, sinon >
           a(j) = a(j - h)
            j = j - h
            If j < m Then Exit Do
         Loop
         a(j) = ref
      Next i
      k = k - 1
   Wend
End Function

Le face à face
Après avoir trouvé sur le web une bonne implémentation de Qsort (Quicksort non récursif), j’ai comparé leur rapidité à trier différentes tailles de tableau.
Les résultats de Shellsort en prenant comme base 100 les résultats de Qsort pour le tri d’entiers long :
Shellsort

Analyse des résultats
Shellsort est plus rapide (jusqu’à 30% plus rapide !) que Qsort pour des tableaux inférieurs à 100 000 valeurs. Au-delà, Qsort creuse petit à petit l’écart.
Compter une dizaine de millisecondes pour trier un tableau de 10 000 valeurs, 160ms pour 100 000 et 2 secondes pour 1 million de valeurs.

Conclusion
En VBA et pour des tableaux jusqu’à 100 000 valeurs, Shellsort est un algorithme de tri très rapide. Si vous possédez une fonction encore plus rapide, merci de l’ajouter en commentaire.

Laisser un commentaire