Le tri par dénombrement

Algorithmique : les tris · niveau 3 (difficile)

Énoncé

Écrire tri_denombrement t k qui trie un tableau d'entiers tous compris entre 0 et k, en $Θ (n + k)$ , sans aucune comparaison.

Corrigé

let tri_denombrement t k =
  let compte = Array.make (k + 1) 0 in
  for i = 0 to Array.length t - 1 do
    compte.(t.(i)) <- compte.(t.(i)) + 1
  done;
  let resultat = Array.make (Array.length t) 0 in
  let pos = ref 0 in
  for v = 0 to k do
    for _j = 1 to compte.(v) do
      resultat.(!pos) <- v;
      pos := !pos + 1
    done
  done;
  resultat

On compte les occurrences de chaque valeur (compte.(v)), puis on réécrit chaque valeur v autant de fois qu'elle apparaît, dans l'ordre croissant. Aucune comparaison : on exploite que les valeurs sont des indices possibles. C'est plus rapide que $Θ (n lo g n)$ , mais au prix d'une hypothèse forte (entiers bornés) et d'un tableau auxiliaire de taille $k + 1$ .

Énoncé

Corrigé

Exercices semblables