Tri comptage - Définition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
La liste des auteurs de cet article est disponible ici.
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;
