Tris de listes de nombres
Spécification commune
tri(Xs,Ys) ssi Ys est une permutation ordonnée croissante de Xs
tri par permutation (permsort)
idée : la spécification !
tri par recherche iteree du minimum (minsort)
idée : le premier élément de Ys est le minimun de Xs, etc.
tri par insertion (insertsort)
idée : on enlève un élément X à Xs, on trie ce qui reste et on place X là où il faut.
tri rapide par pivot (quicksort)
idée : on sélectionne un élément X de Xs, on eclate Xs en deux listes As,
la liste des éléments plus petits que X et Bs,
la liste des éléments plus grands que X, on trie As et Bs, d'où Ys.
tri rapide par fusion (mergesort)
idée : on éclate Xs en deux listes de longueur égale (à peu près),
on trie ces deux listes et on fusionne.
tri par bulles (bubblesort)
Fred Mesnard
