next up previous contents index
Next: Algorithmes n log n Up: Tri par insertion Previous: Implémentation pour des vecteurs   Contents   Index

Implémentation pour des listes

L'implémentation pour les vecteurs est difficile à adapter pour les listes, car elle parcourt les données dans les deux sens, ce qui nécessiterait une liste doublement chaînée.

Une façon de résoudre ce problème est de maintenir deux listes, une correspondant à la partié déjà triée, et l'autre contenant les éléments à insérer.

Il est souhaitable de réutiliser les cellules de la liste d'origine, afin d'éviter des allocations potentiellement coûteuses et des invocations supplémentaires du ramasse-miettes. Ceci veut dire que la liste d'origine sera complètement perturbée. Il est conseillé de ne pas utiliser la liste d'origine après l'invocation de cette implémentation (c'est la règle habituelle concernant les fonctions destructives Common Lisp).



Robert STRANDH
2001-09-28