Il existe de nombreuses méthodes pour trier une liste d'objets : le tri fusion (on sépare une liste en deux, on trie chaque partie puis on regroupe), le tri-bulle (on classe le premier et le second élément, puis le second et le troisième, etc jusqu'au dernier ; on sait alors que le dernier est bien le plus grand et on recommence avec les autres), le tri flash (on sépare la liste en plusieurs intervalles, on trie chaque intervalle avant de recoller), ... Je crois que la fonction List.sort est le tri fusion (info à vérifier...).
On va ici programmer un tri consistant uniquement à retourner un préfixe de la liste (d'où l'appellation : on imagine un cuisinier plaçant sa spatule dans la pile de crêpes et retournant le haut de la pile).
1) Ecrivez une fonction retourne qui reçoit une liste et un nombre n (plus petit que la longueur de la liste) et renvoie la liste en ayant retourné le préfixe de longueur n. Exemple : retourne [1;3;5;8;4] 3 doit rendre [5;3;1;8;4].
On utilise une fonction auxiliaire récursive ayant trois arguments : deux listes li et resu et un entier n. On commence avec n = la longueur du préfixe à retourner, li valant la liste et resu vide. A chaque fois :
si n = 0, on a fini et on rend resu suivie de li.
sinon, on met le premier élément de li au début de resu, on diminue n de 1 et on recommence.
let retourne liste combien =
let rec aux n li resu = if n = 0 then resu@li
else aux (n-1) (List.tl li) ((List.hd li)::(resu))
in aux combien liste [];;
2) Ecrire une fonction cherche_max qui prend une liste et un entier n et qui rend la position du plus grand nombre de la liste entre le début et celui de position n inclus (autrement dit, la position du maximum dans le préfixe de longueur n). On commence l'indexation des listes à 1. Exemples : cherche_max [1;3;5;8;4] 3 rend 3 (position du 5) et cherche_max [1;3;5;8;4] 5 rend 4 (position du 8).
On utilise une fonction auxiliaire récursive ayant quatre arguments dont trois entiers : max_actuel, un indice indiquant la position de ce max, l'endroit où on est (i) et la liste restante. On commence avec le max_actuel valant le premier élément de la liste, l'indice valant 1, i valant 1 et toute la liste. A chaque étape :
si i a dépassé n, on a tout parcouru donc on rend l'indice car il indique l'emplacement du max.
sinon, on considère le premier élément de la liste :
S'il est plus grand que le max_actuel, on actualise max_actuel et on remplace aussi l'indice par celui où on est
Sinon, on garde l'indice et max_actuel.
Dans les deux cas, on ne garde que la queue de la liste et on augmente d'un l'endroit où on est.
let cherche_max liste n =
let rec aux max_actuel position i l =
if i > n then position
else if List.hd l > max_actuel then aux (List.hd l) i (i+1) (List.tl l)
else aux max_actuel position (i+1) (List.tl l)
in aux (List.hd liste) 1 1 liste;;
3) Déduisez-en une fonction un_arrangement qui reçoit une liste et un entier indiquant la longueur du préfixe non trié puis effectue au plus deux retournements pour rendre une liste mieux triée (on diminue de 1 la longueur du préfixe non trié). Autrement dit, la fonction met le maximum en dernière position dans le préfixe. Exemple : un_arrangement [1;4;3;5;8] 3 doit rendre [?;?;4;5;8].
On commence par chercher i le max du préfixe de longueur n.
- si i = n, on n'a rien à faire et on rend directement la liste
- si i = 1, il suffit de retourner l'ensemble du préfixe pour que le max soit à la fin.
- sinon, on retourne d'abord le préfixe de longueur i pour avoir le max en première position puis on retourne le préfixe de longueur n.
Note : on pourrait aussi dans les trois cas faire deux retournements : un jusqu'à i, puis un jusqu'à n. Mais la distinction faite ici permet de faire moins d'opérations.
let un_arrangement liste n =
let i = cherche_max liste n in
if i = n then liste
else if i = 1 then retourne liste n
else retourne (retourne liste i) n;;
4) Déduisez-en la fonction qui trie une liste, testez-la avec [1;3;5;8;4].
Solution
> Haut de la page
