Tri comptage

Un article de Wikipédia, l'encyclopédie libre.

La forme (style, orthographe…) ou le fond (validité des informations, neutralité…) de cet article est à vérifier. Discutez-en ou améliorez-le !
Si vous venez d'apposer le bandeau, veuillez cliquer sur ce lien pour créer la discussion.

Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s'applique à 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 des "0", le nombre des "1", ..., le nombre des "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 temps linéaire, alors qu'un tri par comparaisons nécessite toujours un nombre d'opérations au moins de l'ordre de $n log n$ dans le meilleur des cas.

[modifier] 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

Tableau avant et après triage :

x	1	2	3	4	5
tab[x]	1	27	3	1	3
tab[x] trié	1	1	3	3	27

Tableau de comptage :

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
tab_comptage[x]	0	2	0	2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

[modifier] Algorithme

L'algorithme présenté ici n'est pas la seule solution au problème, et n'est peut-être pas le plus optimal. Le signe ⇐ est utilisé pour les affectations.

Le tableau tab est le tableau à trier, et est passé en paramètre de la fonction tri_par_comptage. La variable borne_superieure, est la valeur entière maximale présente dans tab.

On considère que l'index des tableaux commence à 0.

La fonction tri_par_comptage utilise des variables intermédiaires :

tab_comptage, est un tableau contenant n éléments, n étant la valeur maximale dans tab.
i et j sont des variables de type entier, servant à parcourir les tableaux tab et tab_comptage.

fonction tri_par_comptage(tableau tab, entier borne_superieure)
 
   /* Initialisation des variables */
 
   tab_comptage[borne_superieure + 1]
   taille_tab ⇐ taille(tab) - 1
 
   /* Initialisation du tableau de comptage à 0 */
 
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      tab_comptage[ i ] ⇐ 0
   FinPour
 
   /* Création du tableau de comptage */
 
   Pour i ⇐ 0 Jusqu'à taille_tab
   Faire
      tab_comptage[ tab[ i ] ] ⇐ tab_comptage[ tab[ i ] ] + 1
   FinPour
 
   /* Création du tableau trié */
 
   l ⇐ 0
   Pour i ⇐ 0 Jusqu'à borne_superieure
   Faire
      Pour j ⇐ 1 Jusqu'à tab_comptage[i]
      Faire
         tab[l] = i
         l ⇐ l + 1
      FinPour
   FinPour
 
 Retourne tab