La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparé par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminé. Vous trouverez la réponse que vous souhaitez, à l'aide du code source QuickBASIC suivant :
- OPTION BASE 0
- DIM Tableau(7)
- Tableau(0) = 15
- Tableau(1) = 10
- Tableau(2) = 23
- Tableau(3) = 2
- Tableau(4) = 8
- Tableau(5) = 9
- Tableau(6) = 14
- Tableau(7) = 16
-
- PRINT "Avant:";
- FOR K = 0 TO UBOUND(Tableau)
- PRINT Tableau(K); ",";
- NEXT
-
- Inversion = 0
- Ecart = UBOUND(Tableau) + 1
- DO
- Ecart = INT(Ecart / 2)
- DO
- Inversion = 0
- FOR I = 0 TO (UBOUND(Tableau) + 1) - Ecart - 1
- J = I + Ecart
- IF Tableau(J) < Tableau(I) THEN
- SWAP Tableau(I), Tableau(J)
- Inversion = 1
- END IF
- NEXT
- LOOP UNTIL 1 <> Inversion
- LOOP UNTIL 1 = Ecart
-
- PRINT
- PRINT "Après:";
- FOR L = 0 TO UBOUND(Tableau)
- PRINT Tableau(L); ",";
- NEXT
- PRINT
on obtiendra le résultat suivant :
Avant:15, 10, 23, 2, 8, 9, 14, 16,Après:2, 8, 9, 10, 14, 15, 16, 23,
Voir également
Dernière mise à jour : Mercredi, le 14 septembre 2016