next up previous contents index
Next: Implémentation pour des listes Up: Tri par bulles Previous: Tri par bulles   Contents   Index

Implémentation pour des vecteurs

Notre première implémentation de l'algorithme de tri par bulles s'applique à un vecteur. Elle est générique dans le sens où elle est paramétrée par une fonction de comparaison, passée par argument mot-clé. La valeur par défaut est la fonction <. Elle trie le vecteur destructivement par ordre croissant en utilisant la fonction passée en argument pour déterminer si un élément est inférieur à un autre. Si l'utilisateur passe une fonction de type >, le vecteur sera trié par ordre décroissant. A chaque itération, la fonction cherche l'élément le plus grand (d'après la fonction de comparaison). La voici :

bullesvecteur.lisp

On remarque en particulier l'utilisation de loop et de rotatef pour échanger deux éléments du vecteur. Voici comment on peut s'en servir :

* (defparameter *v* #(4 1 3 1  8 3 44 5 7 3 9 0 0 3 2 44 5 33))

*V*
* *v*

#(4 1 3 1 8 3 44 5 7 3 9 0 0 3 2 44 5 33)
* (bubblesort1 *v*)

NIL
* *v*

#(0 0 1 1 2 3 3 3 3 4 5 5 7 8 9 33 44 44)
* (bubblesort1 *v* :test #'(lambda (x y) (and (oddp x) (evenp y))))

NIL
* *v*

#(1 1 3 3 3 3 5 5 7 9 33 0 0 2 4 8 44 44)
* (bubblesort1 *v* :test #'>)

NIL
* *v*

#(44 44 33 9 8 7 5 5 4 3 3 3 3 2 1 1 0 0)
* (bubblesort1 *v* :test #'(lambda (x y) (and (oddp x) (evenp y))))

NIL
* *v*

#(33 9 7 5 5 3 3 3 3 1 1 44 44 8 4 2 0 0)
*

Cette implémentation est stable, car deux éléments égaux ne sont jamais échangés.


next up previous contents index
Next: Implémentation pour des listes Up: Tri par bulles Previous: Tri par bulles   Contents   Index
Robert STRANDH
2001-09-28