TP5: Tris

Le fichier à remplir est ici.

1 Le tri rapide (Quicksort)

Cette méthode de tri nécessite le partage du reste de la liste originale l en 2 listes l1 et l2 contenant respectivement les éléments inférieurs et les éléments supérieurs ou égaux à la tête de la liste (le pivot). Ces deux listes sont triées récursivement de la même façon et regroupées avec la tête de la liste. Définir une fonction qs l qui renvoie une liste triée en suivant cet algorithme. Attention il faut découper la liste en une passe et ne pas utiliser List.partition.

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

2 Kième plus petit élément

En s'inspirant de la fonction de répartition de quicksort et en raisonnant sur la valeur de k et sur les longueurs de l1 et l2 définir une fonction kieme k l qui retourne le kième élément le plus petit de l (la première position ayant pour indice 0 : kieme 0 l retourne le plus petit élément de l). Attention il ne s'agit pas de trier puis de prendre le kième élément de la liste triée.

Vous pourrez supposer que k est plus petit que la longueur de la liste l.

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

3 Le tri à bulle

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

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

Utiliser cette fonctionnelle pour définir le tri à bulle tribulle l.

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

4 Partition d'un entier n

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=1}^k (j \uparrow P(n-j,j))\) 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 \(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>

5 Pour aller plus loin

  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|]