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).
Solution

> Haut de la page