Implémentation d'algorithmes classiques/Algorithmes de tri/Tri comptage
Apparence
Méthode 1
[modifier | modifier le wikicode]#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
[modifier | modifier le wikicode]//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
[modifier | modifier le wikicode]>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;
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;;
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.