Algorithme Tri par comptage :
Cette méthode consiste a construire un vecteur d’indices ind, dans lequel on calcule la position que devrait avoir chaque élément pour que le vecteur soit trié: PROCEDURE tri_comptage ( v : vec_t; vn : integer; var w : vec_t); VAR i, k : integer; ind : array [1..VMax] of integer; BEGIN { init } for i := 1 to vn do ind[i] := 1; { construit ind } for i := 1 to vn-1 do for k := i+1 to vn do if v[k] < v[i] then ind[i] := ind[i]+1 else ind[k] := ind[k]+1; { construit w } for i := 1 to vn do w[ind[i]] := v[i]; END; Le coût La place occupée est importante (3 vecteurs). Le nombre de comparaisons est constant (vn × (vn − 1)/2). C’est du même ordre que le tri par permutation ou a bulles non optimisé. Il y a très peu d’affectations (vn) ; cela est très intéressant si les éléments de vn sont « lourds », par exemple des strings ou des records triés sur un champ. Voire aussi un petit tuto copier de comment ça marche : Pour i allant de 1 a (fin de tableau) Res(i) = 0 Nb(i) = 0 'calcule des compteurs Pour j allant de 1 a (fin de tableau) Si tableau(j) < tableau(i) alors Nb(i) = nb(i) + 1 Fin de si Fin de pour Fin de pour Pour i allant de 1 a (fin de tableau) j = nb(i) Tant que res(j) <> 0 'cas des doubles j = j + 1 Fin de tant que Res(j) = tableau(i) Fin de pour | Taille : 209KØ Niveau : Intermediaire Auteur : ----- |
|
|