Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tri comptage

Le tri comptage est un algorithme de tri s'appliquant à des valeurs entières.

On suppose qu'on dispose d'un tableau tab composé de 100 entiers entre 0 et 30 (bornes comprises).

Le procédé du tri par comptage est le suivant : on compte le nombre de 0, le nombre de 1, ..., le nombre de 30 présents dans tab, et on reconstruit tab en y ajoutant les valeurs selon leur quantité croissante (on ne trie pas les valeurs mais le comptage de ces valeurs au sein du tableau).

La restriction très particulière imposée à ses valeurs d'entrée en fait un tri en N, alors qu'un tri général est nécessairement d'ordre N log (N).

Exemple

le tableau de 5 entiers 1, 27, 3, 1, 3 contient 2 fois 1, 2 fois 3 et 1 fois 27, le tableau trié par la méthode du tri comptage est donc : 1, 1, 3, 3, 27