Tri comptage — Wikipédia

Cet article ne cite pas suffisamment ses sources (mai 2020).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Tri comptage

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	${\displaystyle O(n+k)}$

Complexité en espace

Pire cas	${\displaystyle O(n+k)}$

modifier - modifier le code - modifier Wikidata

Le tri comptage (counting sort en anglais), appelé aussi tri casier, est un algorithme de tri par dénombrement qui s'applique sur des valeurs entières.

Le principe repose sur la construction de l'histogramme des données, puis le balayage de celui-ci de façon croissante, afin de reconstruire les données triées. Ici, la notion de stabilité n'a pas réellement de sens, puisque l'histogramme factorise les données – plusieurs éléments identiques seront représentés par un unique élément quantifié. Ce tri ne peut donc pas être appliqué sur des structures complexes, et il convient exclusivement aux données constituées de nombres entiers compris entre une borne min et une borne max connues. Dans un souci d'efficacité, celles-ci doivent être relativement proches l'une de l'autre, ainsi que le nombre d'éléments doit être relativement grand.

Dans cette configuration, et avec une distribution de données suivant une loi uniforme discrète, ce tri est le plus rapide (on troque, en quelque sorte, du temps de calcul contre de la mémoire). La restriction très particulière imposée à ses valeurs d'entrée en fait un tri en temps linéaire^[1], alors qu'un tri par comparaisons optimal nécessite un nombre d'opérations de l'ordre de ${\displaystyle n\log n}$.

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).

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 :

Tableau de comptage :

L'algorithme présenté ici n'est pas la seule solution au problème, et n'est peut-être pas optimal. On considère que l'index des tableaux commence à 0. Le signe = est utilisé pour les affectations. Le tableau tab est le tableau à trier, et est passé en paramètre de la fonction triParComptage. La variable borneSuperieure, est la valeur entière maximale présente dans tab.

La fonction triParComptage utilise des variables intermédiaires :

• tabComptage, 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 tabComptage.

fonction triParComptage(tab):    // détermination de "borneSuperieure" la valeur entière maximale présente dans tab    borneSuperieure = 0    Pour tout k de tab          si k > borneSuperieure               borneSuperieure = k          finSi    finPour     // Initialisation du tableau de comptage à 0    pour i = 0 à borneSuperieure       tabComptage[i] = 0    finPour    // Création du tableau de comptage    Pour tout k de tab           tabComptage[k] = tabComptage[k] + 1           finPour     // Création du tableau trié    N = taille de tabComptage    cpt = 0    pour i = 0 à N       pour j = 0 à tabComptage[i]            tabTrie[cpt] = i            cpt = cpt + 1      finPour   finPour    retourne tabTrie 

Voici le code en python exécutable :

def TriComptage(tab):     # détermination de "borneSuperieure" la valeur entière maximale présente dans tab     borneSuperieure = 0     for k in tab:         if k>borneSuperieure:             borneSuperieure = k      # Initialisation du tableau de comptage à 0     tabComptage = [0]*(borneSuperieure+1)          # Création du tableau de comptage     for k in tab:         tabComptage[k]=tabComptage[k]+1              # Création du tableau trié         tabTrie=[]      N = len(tabComptage)     for i in range(N):         for j in range(tabComptage[i]):             tabTrie.append(i)     return tabTrie 

• Tri de nombres entiers

https://visualgo.net/en/sorting

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l’informatique
• Portail de l'informatique théorique