Algorithmique des structures de données arborescentes 2017-2018

La fonction List.sort prend deux arguments : la liste à trier est le 2ème argument. On lui passe en 1er argument une fonction de comparaison, qui indique le critère de tri. Ce 1er argument de List.sort influence donc l'ordre dans lequel on trie la liste. 

La fonction de comparaison à passer en 1er argument à List.sort prend deux paramètres et doit renvoyer

• un entier négatif si on veut que dans la liste triée, le 1er paramètre apparaisse avant le 2ème, autrement dit, si le 1er paramètre doit être considéré comme plus petit que le 2ème.
• un entier positif si on veut que dans la liste triée, le 2ème paramètre apparaisse avant le 1er.
• 0 si la comparaison considère les deux éléments comme égaux.

Exemples :

1. si la fonction passée en premier paramètre de List.sort est let comparaison x y = x - y, alors List.sort comparaison [1; 3; 2; 4; 5] renvoie [1; 2; 3; 4; 5] En effet, comparaison x y est négatif lorsque x < y, et dans ce cas, x apparaîtra avant y.
2. si la fonction passée en premier paramètre de List.sort est let comparaison x y = y - x, alors List.sort comparaison [1; 3; 2; 4; 5] renvoie [5; 4; 3; 2; 1].
3. si la fonction passée en premier paramètre de List.sort est

   let comparaison x y = match (x mod 2), (y mod 2) with
   | 0,1 -> -1
   | 1,0 -> 1
   | 0,0 | 1,1 -> x-y       

   alors List.sort comparaison [1; 3; 2; 4; 5] renvoie [2; 4; 1; 3; 5] : les entiers pairs sont considérés plus petits que les entiers impairs, et si la parité est identique, on trie dans l'ordre croissant.
4. enfin,

   List.sort (fun (c,x) (d,y) -> x - y) [('o',1); ('c', 3); ('a', 2); ('m', 4); ('l', 5)]

   renvoie

   [('o', 1); ('a', 2); ('c', 3); ('m', 4); ('l', 5)]

   (tri dans l'ordre croissant de la 2ème composante), alors que

   List.sort (fun (c,x) (d,y) -> int_of_char c - int_of_char d) [('o',1); ('c', 3); ('a', 2); ('m', 4); ('l', 5)]

   renvoie

   [('a', 2); ('c', 3); ('l', 5); ('m', 4); ('o', 1)]

   (tri dans l'ordre croissant de la 1ère composante).