« 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 : | Ligne 1 : | ||
== [[Programmation C|C]] == |
|||
{{feuille volante}} |
|||
=== Méthode 1 === |
|||
<code> |
|||
<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> |
//On ne compte que des valeurs variant de 0 à 255 <br> |
||
unsigned int counter[256];<br> |
unsigned int counter[256];<br> |
||
Ligne 7 : | Ligne 29 : | ||
void countersort(unsigned char* table,unsigned int n)<br> |
void countersort(unsigned char* table,unsigned int n)<br> |
||
{ |
{ |
||
unsigned int i,k,j; |
unsigned int i,k,j; |
||
<br> |
|||
//Mise à zéro du compteur |
//Mise à zéro du compteur |
||
for(i=0;i<256;i++) counter[i]=0; |
for(i=0;i<256;i++) counter[i]=0; |
||
<br> |
|||
//Dénombrement des éléments |
//Dénombrement des éléments |
||
for(i=0;i<n;i++) counter[table[i]]++; |
for(i=0;i<n;i++) counter[table[i]]++; |
||
<br> |
|||
//On replace les éléments dans le tableau |
//On replace les éléments dans le tableau |
||
j=0; |
j=0; |
||
for(i=0;i<256;i++) |
for(i=0;i<256;i++) |
||
{ |
{ |
||
//Il y a counter[i] éléments ayant la valeur i |
//Il y a counter[i] éléments ayant la valeur i |
||
for(k=0;k<counter[i];k++,j++) |
for(k=0;k<counter[i];k++,j++) |
||
table[j]=i; |
table[j]=i; |
||
} |
} |
||
} |
} |
||
</ |
</source> |
||
== 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: |
[[Catégorie:Implémentation d'algorithmes classiques (livre)]] |
Version du 23 novembre 2010 à 14:27
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 <br>
unsigned int counter[256];<br>
//Algorithme linéaire de tri compteur<br>
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
>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.