On présente ici un exemple de tri qui exploite les dictionnaires.

On se donne un tableau tab contenant des nombres entiers. Cette méthode de tri sera efficace si l'écart entre le minimum et le maximum n'est pas trop important.

FONCTION tri_denombrement
ENTRÉE: tab, tableau à trier
SORTIE: copie de tab, triée
DÉBUT
  SI tab est vide ALORS
    RENVOYER []
  FIN
  soit d un dictionnaire vide,
  soit m égal à tab[0] # ce sera le min
  soit M égal à tab[0] # ce sera le max
  POUR CHAQUE item DE tab FAIRE
    SI item dans d ALORS
      ajouter 1 à la valeur associer à item dans d
    SINON
      insérer la nouvelle clé item dans d avec la valeur 1
    FIN
    SI item > M ALORS
      M = item
    FIN
    SI item < m ALORS
      m = item
    FIN
  FIN
  soit t un tableau vide
  POUR v allant de m à M FAIRE
    SI v est dans dico ALORS
      soit k la valeur associée à v dans dico
      ajouter k fois la valeur v dans t
    FIN
  FIN
  RENVOYER t
FIN

1. Pourquoi est-il préférable que l'écart entre minimum et maximum soit faible ?
2. Implémentez cet algorithme et testez.