« Implémentation d'algorithmes classiques/Algorithmes de tri/Tri comptage » : différence entre les versions
Contenu supprimé Contenu ajouté
m a déplacé Tri par dénombrement vers Implémentation d'algorithmes classiques/Algorithmes de tri/Tri comptage : rangement |
Aucun résumé des modifications |
||
Ligne 1 :
== [[Programmation C|C]] ==
=== Méthode 1 ===
<source lang=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);
}
</source>
=== Méthode 2 ===
<source lang="C">
//On ne compte que des valeurs variant de 0 à 255 <br>
unsigned int counter[256];<br>
Ligne 7 ⟶ 29 :
void countersort(unsigned char* table,unsigned int n)<br>
{
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 ==
<source lang=matlab>
>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;
</source>
== [[Objective Caml]] ==
<source lang=ocaml>
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;;
</source>
== [[Programmation Pascal|Pascal]] ==
<source lang=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;
</source>
<small>Tout ou partie de cette page est issue de l'article Wikipédia « [[w:Tri comptage|Tri comptage]] » dans sa [http://fr.wikipedia.org/w/index.php?title=Tri_comptage&oldid=54854805 version du 2 juillet 2010].</small>
[[Catégorie:
| |||