Tri par tas

Exercice · OCaml (option informatique), chapitre 19 — Files de priorité : le tas binaire

Énoncé

Écrire tri_par_tas arr qui trie un tableau d'entiers à l'aide d'un tas.

Corrigé

let tri_par_tas arr =
  let n = Array.length arr in
  let t = cree n in
  for i = 0 to n - 1 do insere t arr.(i) done;       (* tout insérer *)
  for i = 0 to n - 1 do arr.(i) <- extrait_min t done (* extraire dans l'ordre *)

On insère tous les éléments dans un tas, puis on les extrait : l'extraction du minimum à répétition les rend dans l'ordre croissant. $n$ insertions et $n$ extractions, chacune en $Θ (lo g n)$ , soit $Θ (n lo g n)$ — la même garantie que le tri fusion (chapitre 9).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.