Tri par tas

On choisit d'implémenter un tri croissant par un tri par tas, en utilisant un tas max implémenté par un type array OCaml.

1. 1

   Indice

   Utiliser une variable temporaire pour conserver la valeur d'un élément avant de faire l'échange.
   Écrire une fonction echanger : 'a array -> int -> int -> unit qui échange en place les éléments des indices i et j du tableau t. Par exemple let a = [|1;2;3|] in echanger a 0 2; a renvoie () et modifie le tableau en [|3; 2; 1|].
2. 2

   Indice

   Identifier le plus grand élément parmi le nœud et ses enfants puis échanger récursivement si nécessaire.
   Écrire une fonction tamiser : 'a array -> int -> int -> unit qui tamise en place le sous-arbre d'indice i pour respecter la propriété d'un tas maximum. Par exemple let a = [|1;3;2|] in tamiser a 3 0; a renvoie () et modifie le tableau en [|3; 1; 2|].
3. 3

   Indice

   Parcourir les nœuds internes de bas en haut afin d'appliquer systématiquement l'opération de tamisage.
   Écrire une fonction construire_tas_max : 'a array -> unit qui transforme en place un tableau arbitraire en un tas maximum valide. Par exemple let a = [|1;3;2;4;5;6|] in construire_tas_max a; a renvoie () et modifie donne [|6; 5; 4; 1; 3; 2|].
4. 4

   Indice

   Extraire le maximum et le placer à la fin du tableau, puis réajuster la structure et répéter l'opération avec le début de la structure.
   Écrire une fonction trier_par_tas : 'a array -> unit qui trie un tableau en ordre croissant en utilisant les fonctions précédentes et le tri par tas. Par exemple let a = [|3;1;4;2|] in trier_par_tas a; a renvoie () et modifie le tableau en [|1; 2; 3; 4|].