Basic

Auteur : Bernard Marcelly (c) 2003

Objet de la macro TriShell

Elle permet de trier par valeur alphabétique croissante un tableau de chaînes de caractères, avec une rapidité convenable.

La macro TriShell, ainsi que d’autres tris, sont dans le module Tris de la bibliothèque macros dans ce document Writer.

Explications

L’algorithme le plus souvent reproduit est le “ tri Bulle ” (anglais : Bubble Sort), qui a l’inconvénient d’être extrêmement lent.

L’algorithme du “ tri Rapide ” (anglais : Quick Sort) est le plus efficace sur les grands tableaux, mais utilise la récursion, qui n’est que partiellement supportée par OOo Basic, à partir de la version 1.1

L’algorithme décrit par D. L. Shell en 1959 est assez rapide, n’utilise pas la récursion, et reste assez simple.

De nombreux sites Internet décrivent les différents tris. Je me suis inspiré des algorithmes Pascal listés à la page http://www-lm2s.utt.fr/~doussot/algo_pascal/pas080.html

Performances

La macro Main du module Tris permet de mesurer la durée de tri d’un tableau de valeurs aléatoires et de vérifier que le résultat est effectivement trié. Les durées obtenues sont bien plus élevées que celles indiquées dans la page Internet citée, car Basic est un langage interprété.

J’ai obtenu les résultats suivants sous Windows XP avec un PC portable doté d’un processeur Athlon Mobile 2000 XP+. Des tableaux non aléatoires (partiellement trié, ou trié en inverse) donneraient des résultats différents.

Algorithme	Nombre d’éléments	Durée en secondes
Tri Bulle	100 6 200 20 500 300
Tri Bulle amélioré	100 2 200 12 500 196
Tri Shell	2000 4 5000 10 10000 25 16300 43

Codage du tri Shell

Sub TriShell(Atrier())

Dim k1 As Integer, k2 As Integer, taille As Integer

Dim x1 As Integer, enOrdre As Boolean

Dim echange

taille = UBound(Atrier()) +1 -LBound(Atrier())

k1 = Fix(taille /2)

do while k1 > 0

k2 = UBound(Atrier()) - k1

enOrdre = true

for x1 = LBound(Atrier()) to k2

if Atrier(x1) > Atrier(x1 +k1) then

echange = Atrier(x1)

Atrier(x1) = Atrier(x1 +k1)

Atrier(x1 +k1) = echange

enOrdre = false

end if

next

if enOrdre then

k1 = Fix(k1 /2)

end if

loop

End Sub

Macro Tri Shell

Sophie Gautier

2003-09-07T19:13:36