Tri par dénombrement

Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s'applique sur des valeurs entières.

Définition

Le principe repose sur la construction de l'histogramme des données, puis le balayage de celui-ci de façon croissante, afin de reconstruire les données triées.

Ici, la notion de stabilité (tri stable) n'a pas réllement de sens, puisque l'histogramme factorise les données (c.a.d plusieurs éléments identiques seront représentés par un unique élément quantifié). Ce tri ne peut donc pas être appliqué sur des structures complexes, et il convient exclusivement aux données constituées de nombres entiers compris entre une borne min et une borne max connues. Dans un souci d'efficacité, celles-ci doivent être relativement proches l'une d'elle, ainsi que le nombre d'éléments doit être relativement grand.

Dans cette configuration, et avec une distribution de données suivant une loi uniforme, ce tri est le plus rapide (on troque, en quelque sorte, du temps de calcul contre de la mémoire).

La restriction très particulière imposée à ses valeurs d'entrée en fait un tri en temps linéaire, alors qu'un tri par comparaisons optimal nécessite un nombre d'opérations de l'ordre de nlogn.

Exemple

On suppose qu'on dispose d'un tableau tab composé de 100 entiers entre 0 et 30 (bornes comprises).

Le procédé du tri par comptage est le suivant : on compte le nombre des "0", le nombre des "1", ..., le nombre des "30" présents dans tab, et on reconstruit tab en y ajoutant les valeurs selon leur quantité croissante (on ne trie pas les valeurs mais le comptage de ces valeurs au sein du tableau).

Le tableau de 5 entiers 1, 27, 3, 1, 3 contient 2 fois 1, 2 fois 3 et 1 fois 27, le tableau trié par la méthode du tri comptage est donc : 1, 1, 3, 3, 27

Tableau avant et après triage :

Tableau de comptage :

Algorithme

L'algorithme présenté ici n'est pas la seule solution au problème, et n'est peut-être pas le plus optimal. Le signe ⇐ est utilisé pour les affectations.

Le tableau tab est le tableau à trier, et est passé en paramètre de la fonction tri_par_comptage. La variable borne_superieure, est la valeur entière maximale présente dans tab.

On considère que l'index des tableaux commence à 0.

La fonction tri_par_comptage utilise des variables intermédiaires :

• tab_comptage, est un tableau contenant n éléments, n étant la valeur maximale dans tab.
• i et j sont des variables de type entier, servant à parcourir les tableaux tab et tab_comptage.

fonction tri_par_comptage(tableau tab, entier borne_superieure)
 
   /* Initialisation des variables */
 
   tab_comptage[borne_superieure + 1]
   taille_tab ⇐ taille(tab) - 1
 
   /* Initialisation du tableau de comptage à 0 */
 
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      tab_comptage[ i ] ⇐ 0
   FinPour
 
   /* Création du tableau de comptage */
 
   Pour i ⇐ 0 Jusqu'à taille_tab
   Faire
      tab_comptage[ tab[ i ] ] ⇐ tab_comptage[ tab[ i ] ] + 1
   FinPour
 
   /* Création du tableau trié */
 
   l ⇐ 0
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      Pour j ⇐ 1 Jusqu'à tab_comptage[i]
      Faire
         tab[l] = i
         l ⇐ l + 1
      FinPour
   FinPour
 
 Retourne tab

Implémentation

L'implémentation en langage Pascal :

const 
    base = 10;
    MAX_COUNT = 20;
 
type
    count_tab=array [0..base-1] of integer;
    tab_entier = array [1..MAX_COUNT] of integer;
 
procedure tri_comptage(n : integer ; var t : tab_entier);
var
    t2 : tab_entier;
    c : count_tab;
    i, v : integer;
begin
    Writeln; Writeln('Tri Comptage'); Writeln; 
    for i:=0 to base-1 do c[i] := 0;
    for i:=1 to n do begin
        v := t[i];
        c[v] := c[v] + 1;
    end;
    for i:=1 to base-1 do c[i] := c[i]+c[i-1];
    for i:=1 to n do begin
        v := t[i];
        t2[c[v]] := t[i];
        c[v] := c[v] - 1;
    end;
 
    copier_tableau(n, t2, t);
end;

L'implémentation est triviale en C :

#define MAX 256 // borne min = 0 et borne max = 255 incluses
 
void tri_hist(int t[], int len)
{
	int i, j, k;
	int * hist = calloc(MAX, sizeof(int));
 
	for(i=0; i < len; i++)
		hist[ t[i] ]++;
 
	k=0;
	for(i=0; i < MAX; i++)
		for(j=0; j < hist[i]; j++)
			t[k++] = i;
 
	free(hist);
}

La même chose en Objective Caml :

let tri_hist tab =
  (* Création et initialisation de hist avec des 0 *)
  let hist = Array.make 256 0 in
    (* Remplissage de hist *)
    Array.iter (fun x -> hist.(x) <- hist.(x) + 1) tab;
    (* Mise en ordre du tableau initial *)
    let k = ref 0 in
      Array.iteri (fun i x -> Array.fill tab !k x i; k := !k + x) hist;;

Ou bien en Maple :

>tri:=proc(L)
> 
>  m:=min(L); M:=max(L);
>  n:=M-m+1;
>  A:=[0$n];
>  B:=[];
> 
>  for i from 1 to nops(L) do
>    A[L[i]-m+1]:=A[L[i]-m+1]+1;
>  od;
> 
>  for j from 1 to n do
>    B:=[op(B),(m+j-1)$(A[j])]; 
>  od;
>
> RETURN(B);
 
> end;