Implémenter des algorithmes de tri avancés, Excel VBA
Voici une explication détaillée pour implémenter des algorithmes de tri avancés en VBA Excel, en mettant l’accent sur deux algorithmes de tri bien connus : QuickSort et MergeSort. Je vais vous guider étape par étape sur la façon de les implémenter dans VBA avec des explications détaillées.
1. Algorithme QuickSort en VBA
QuickSort est un algorithme de tri par diviser pour régner. Il fonctionne en choisissant un élément pivot, en partitionnant les autres éléments autour de ce pivot, puis en triant récursivement les sous-tableaux.
Étapes pour implémenter QuickSort en VBA :
1. Choisir un pivot (généralement le dernier élément).
2. Partitionner le tableau en deux sous-tableaux : les éléments inférieurs au pivot et ceux supérieurs.
3. Appliquer récursivement la méthode de tri aux deux sous-tableaux.
Voici comment vous pouvez l’implémenter en VBA :
Sub ExempleQuickSort()
Dim arr As Variant
arr = Array(3, 7, 8, 5, 2, 1, 4, 6) ' Tableau d'exemple
' Appeler la fonction QuickSort
QuickSort arr, LBound(arr), UBound(arr)
' Afficher le tableau trié dans la fenêtre immédiate (Ctrl + G)
For i = LBound(arr) To UBound(arr)
Debug.Print arr(i)
Next i
End Sub
' Fonction QuickSort
Sub QuickSort(ByRef arr As Variant, ByVal low As Long, ByVal high As Long)
Dim pivot As Long
Dim i As Long, j As Long
Dim temp As Variant
If low < high Then
' Choisir un pivot et partitionner le tableau
pivot = Partition(arr, low, high)
' Tri récursif des sous-tableaux
QuickSort arr, low, pivot - 1
QuickSort arr, pivot + 1, high
End If
End Sub
' Fonction de partition pour réarranger les éléments autour du pivot
Function Partition(ByRef arr As Variant, ByVal low As Long, ByVal high As Long) As Long
Dim pivot As Variant
Dim i As Long, j As Long
Dim temp As Variant
pivot = arr(high) ' Le dernier élément est le pivot
i = low - 1 ' Pointeur pour les éléments inférieurs au pivot
For j = low To high - 1
If arr(j) <= pivot Then
i = i + 1
' Échanger arr(i) et arr(j)
temp = arr(i)
arr(i) = arr(j)
arr(j) = temp
End If
Next j
' Échanger arr(i + 1) et arr(high) (le pivot)
temp = arr(i + 1)
arr(i + 1) = arr(high)
arr(high) = temp
Partition = i + 1 ' Retourner l'indice du pivot
End Function
Explication du code QuickSort :
1. Sous-routine QuickSort :
- Cette sous-routine prend un tableau arr et le trie en place.
- Elle appelle la fonction Partition pour réarranger le tableau puis trie récursivement les sous-tableaux.
- low et high sont les indices qui indiquent le sous-tableau actuellement trié.
2. Fonction Partition :
- Le pivot est sélectionné comme étant le dernier élément du sous-tableau (arr(high)).
- Elle réorganise les éléments pour que tous les éléments inférieurs au pivot se trouvent à gauche et tous les éléments supérieurs à droite.
- Elle retourne l’indice du pivot, qui divise le tableau en deux sous-tableaux.
2. Algorithme MergeSort en VBA
MergeSort est également un algorithme de tri par diviser pour régner. Il divise le tableau en deux sous-tableaux, les trie récursivement, puis les fusionne pour obtenir un tableau trié.
Étapes pour implémenter MergeSort en VBA :
1. Diviser le tableau en deux moitiés.
2. Trier récursivement les deux moitiés.
3. Fusionner les deux sous-tableaux triés.
Voici comment l’implémenter en VBA :
Sub ExempleMergeSort()
Dim arr As Variant
arr = Array(3, 7, 8, 5, 2, 1, 4, 6) ' Tableau d'exemple
' Appeler la fonction MergeSort
MergeSort arr, LBound(arr), UBound(arr)
' Afficher le tableau trié dans la fenêtre immédiate (Ctrl + G)
For i = LBound(arr) To UBound(arr)
Debug.Print arr(i)
Next i
End Sub
' Fonction MergeSort
Sub MergeSort(ByRef arr As Variant, ByVal low As Long, ByVal high As Long)
Dim mid As Long
If low < high Then
mid = (low + high) \ 2 ' Trouver le milieu du tableau
' Trier récursivement les moitiés gauche et droite
MergeSort arr, low, mid
MergeSort arr, mid + 1, high
' Fusionner les deux moitiés triées
Merge arr, low, mid, high
End If
End Sub
' Fonction Merge pour fusionner deux moitiés triées
Sub Merge(ByRef arr As Variant, ByVal low As Long, ByVal mid As Long, ByVal high As Long)
Dim tempArr() As Variant
Dim i As Long, j As Long, k As Long
Dim leftSize As Long, rightSize As Long
leftSize = mid - low + 1
rightSize = high - mid
' Créer des tableaux temporaires pour les deux moitiés
ReDim leftArr(leftSize - 1)
ReDim rightArr(rightSize - 1)
' Copier les données dans les tableaux temporaires
For i = 0 To leftSize - 1
leftArr(i) = arr(low + i)
Next i
For j = 0 To rightSize - 1
rightArr(j) = arr(mid + 1 + j)
Next j
i = 0
j = 0
k = low
' Fusionner les tableaux temporaires dans le tableau original
While i < leftSize And j < rightSize
If leftArr(i) <= rightArr(j) Then
arr(k) = leftArr(i)
i = i + 1
Else
arr(k) = rightArr(j)
j = j + 1
End If
k = k + 1
Wend
' Copier les éléments restants de leftArr ou rightArr
While i < leftSize
arr(k) = leftArr(i)
i = i + 1
k = k + 1
Wend
While j < rightSize
arr(k) = rightArr(j)
j = j + 1
k = k + 1
Wend
End Sub
Explication du code MergeSort :
1. Sous-routine MergeSort :
- Cette sous-routine divise récursivement le tableau en deux moitiés jusqu’à ce que chaque sous-tableau ait une seule valeur.
- Elle appelle ensuite la fonction Merge pour fusionner les sous-tableaux triés.
2. Fonction Merge :
- La fonction Merge fusionne deux sous-tableaux triés en un seul tableau trié.
- Elle utilise des tableaux temporaires (leftArr et rightArr) pour stocker les deux moitiés du tableau et les fusionner dans l’ordre.
Comment utiliser ces algorithmes de tri :
- Vous pouvez appeler la procédure ExempleQuickSort ou ExempleMergeSort dans l’éditeur VBA pour tester ces algorithmes de tri.
- Vous pouvez remplacer le tableau d’exemple arr par n’importe quelle plage de données dans Excel, par exemple :
arr = Range("A1:A10").Value ' Obtenir les valeurs des cellules A1 à A10
Assurez-vous que la plage contient des données numériques pour le tri.
Conclusion :
Les algorithmes QuickSort et MergeSort sont deux des algorithmes de tri les plus efficaces. QuickSort est généralement plus rapide en raison de sa stratégie de partition, mais MergeSort est plus prévisible en termes de performance car il garantit une complexité en temps de O(n log n) dans le pire des cas. Vous pouvez implémenter l’un ou l’autre de ces algorithmes dans VBA selon vos besoins et la taille des données à trier.