TP5: Tris

Implémenter une fonction split v l prenant en argument un pivot v et une liste l et retournant deux listes : une contenant les éléments de l strictement plus plus petits que v, et une autre avec les éléments plus grand ou égaux, dans le même ordre que l. Il est interdit d'utiliser List.partition ou List.filter. Cette fonction devra être polymorphe (c'est à dire accepter des listes de tous types).

val split : 'a -> 'a list -> 'a list * 'a list = <fun>

Le tri rapide consiste à partitionner la queue de la liste l en entrée en deux listes l1 et l2 en utilisant comme pivot le premier élément v de l. Les éléments de l1 sont donc tous plus petits que v, et ceux de l2 sont plus grands ou égaux. Pour trier la liste, il faut alors récursivement trier les listes l1 et l2, puis réassembler le tout.

Définir une fonction qs l qui renvoie une liste triée en suivant cet algorithme.

val qs : 'a list -> 'a list = <fun>

Imaginez que vous avez une liste et que vous vouliez trouver le kième élément le plus petit de cette liste. Une solution simple est de trier la liste puis de chercher le kième élément. Une solution plus efficace s'appuie sur la fonction split définie ci-dessus, en comparant la taille de la première liste retournée et la valeur de k. Attention, le plus petit élément est retourné pour k valant 1.

Vous pourrez supposer que k est inférieur ou égal à la longueur de la liste l, en utilisant assert false pour indiquer les cas impossibles.

val kieme : int -> 'a list -> 'a = <fun>

Cette méthode consiste à parcourir plusieurs fois la liste en échangeant les éléments contigus non ordonnés (cet algorithme peut être visualisé ici, cliquer sur « sort » puis « go »).

Le tri à bulle étant basé sur un algorithme s'exécutant jusqu'à ce que l'ordre ne change plus, définir une fonctionnelle jqastable x f qui applique f à son argument tant que le résultat diffère (tant que f x est différent de x). Rappel, en OCaml, on teste l'égalité avec = et la différence avec <>.

val jqastable : 'a -> ('a -> 'a) -> 'a = <fun>

Écrire une fonction unebulle qui prend une liste l en entrée et effectue l'algorithme suivant :

• si la liste est vide ou a un élément, retourner la liste,
• sinon, considérer les deux premiers éléments, et les échanger pour qu'ils soient dans l'ordre, puis appeler récursivement sans le premier élément.

val unebulle : 'a list -> 'a list = <fun>

Utiliser ces fonctions pour définir le tri à bulle tribulle l, qui consiste à appliquer unebulle jusqu'à ce que le résultat ne change plus.

val tribulle : 'a list -> 'a list = <fun>

Un entier naturel non nul \(n\) peut être décomposé de différentes façons en somme d'entiers naturels non nuls.

Par exemple: \(5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1\). Selon cet exemple il existe 7 partitions (manières différentes de décomposer) de 5.

Nous allons représenter une partition par la liste des entiers qu'elle comporte: une partition de 5 est [4;1]. Une autre partition de 5 est [2;2;1]. Attention : une partition est toujours ordonnée des nombres les plus grands vers les plus petits. La liste [2;2;1] est une partition, mais les listes [1;2;2] ou [2;1;2] n'en sont pas.

Notons \(P(n,k)\) la liste des partitions de l'entier \(n\) contenant des entiers au plus égaux à \(k\). Par exemple, \(P(5,1)\) est la liste de partitions [ [1;1;1;1;1] ], et \(P(5,2)\) est la liste de partitions [ [1;1;1;1;1]; [2;1;1;1]; [2;2;1] ]. La liste de partitions d'un entier \(n\) est alors \(P(n,n)\).

Nous définissions \(P(n,k)\) comme suit:

1. \(P(0,0) = [ [] ]\);
2. \(P(n,0) = []\) si \(n > 0\);
3. \(P(n,k)\) = \(P(n,n)\) si \(k > n\);
4. \(P(n,k)\) = \(\bigoplus [(j \uparrow P(n-j,j)) \mid j \in [1..k]]\) sinon.

L'opération \(\bigoplus l1\;l2\;..\;ln\) réalise la concaténation de toutes les listes en argument: l1 @ l2 @ .. @ ln. Programmer la fonction merge ll qui réalise cette opération.

val merge : 'a list list -> 'a list = <fun>

L'opération \([ f | j \in [1..k] ]\), où f est une fonction d'argument j, fabrique la liste [f 1; …; f k]. Programmer la fonction create f k qui réalise cette opération (on supposera toujours commencer à \(1\)).

val create : (int -> 'a) -> int -> 'a list = <fun>

L'opération \(j \uparrow ll\) prend la liste de listes \(ll\) et ajoute \(j\) en tête de chaque liste. Programmer la fonction insert j ll qui réalise cette opération.

val insert : 'a -> 'a list list -> 'a list list = <fun>

Définir la fonction partition n qui donne la liste des partitions de n.

val partition : int -> int list list = <fun>

1. Définir partition en récursion terminale. Il sera peut-être nécessaire de modifier insert.
2. Essayer de résoudre le problème https://projecteuler.net/problem=78 avec votre langage de programmation favori (OCaml étant bien sûr une option).

3. Écrire quicksort en utilisant des tableaux, et chercher à optimiser l'utilisation mémoire.

   val quicksort : 'a array -> unit = <fun>
   

   let _ =
     let a = [|4; 12; 27; -12; 7; 8; 1; 3; 6; 12; 42|] in
     quicksort a; a
   

   - : int array = [|-12; 1; 3; 4; 6; 7; 8; 12; 12; 27; 42|]