Implémentation d'algorithmes classiques/Algorithmes de tri/Tri comptage

C

Méthode 1

#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);
}

Méthode 2

//On ne compte que des valeurs variant de 0 à 255
unsigned int counter[256];

//Algorithme linéaire de tri compteur
void countersort(unsigned char* table,unsigned int n)
{
	unsigned int i,k,j;

	//Mise à zéro du compteur
	for(i=0;i<256;i++) counter[i]=0;

	//Dénombrement des éléments
	for(i=0;i<n;i++) counter[table[i]]++;

	//On replace les éléments dans le tableau
	j=0;
	for(i=0;i<256;i++)
	{
		//Il y a counter[i] éléments ayant la valeur i
		for(k=0;k<counter[i];k++,j++)
			table[j]=i;
	}
}

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;

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;;

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;

Tout ou partie de cette page est issue de l'article Wikipédia « Tri comptage » dans sa version du 2 juillet 2010.