Counting Sort

Q: Quelle est la complexité temporelle du tri par comptage ?

Le tri par comptage est en `O(n + k)`, où `n` est le nombre d'éléments et `k` la plage des valeurs possibles. Lorsque `k = O(n)`, c'est un temps linéaire. Il utilise `O(n + k)` d'espace supplémentaire.

Q: Le tri par comptage est-il stable ?

Il peut l'être. La version stable construit les sommes préfixes des comptes et place les éléments de droite à gauche, ce qui préserve l'ordre relatif des clés égales. La version simple « réécriture par valeur » montrée ici produit un tri correct mais est surtout utilisée pour des entiers simples.

Q: Quand devrais-je utiliser le tri par comptage ?

Utilisez-le pour trier des entiers (ou des clés convertibles en entiers) dans une plage petite et connue. Si la plage de valeurs `k` est bien plus grande que le nombre d'éléments, le tableau de comptage gaspille de la mémoire et un tri par comparaison est préférable.

Q: Quelle est la différence entre le tri par comptage et le tri par base (radix sort) ?

Le tri par comptage trie sur la valeur entière en une seule passe et nécessite un tableau de comptage aussi grand que la plage de valeurs. Le tri par base trie chiffre par chiffre et appelle généralement un tri par comptage stable sur chaque chiffre, ce qui maintient une petite plage par passe (par exemple `10` pour les chiffres décimaux). Le tri par base gère de grandes plages de valeurs qui rendraient un seul tri par comptage impraticable.

Q: Pourquoi le tri par comptage n'est-il pas toujours plus rapide que le tri rapide (quicksort) ?

Le tri par comptage est en `O(n + k)`, il ne gagne donc que lorsque la plage de valeurs `k` est comparable à `n`. Si `k` est énorme - par exemple trier 100 valeurs dans la plage de `0` à `1,000,000,000` - le tableau de comptage en `O(k)` domine et gaspille de la mémoire, tandis qu'un tri par comparaison en `O(n log n)` comme le quicksort reste rapide et économe en espace.

Q: Le tri par comptage peut-il gérer les nombres négatifs ?

Oui, avec un petit décalage. Au lieu d'indexer le tableau de comptage directement par la valeur, indexez-le par `value - min`, de sorte que la plus petite valeur corresponde à l'indice `0`. La taille du tableau de comptage devient `max - min + 1`. Oublier ce décalage est une erreur courante qui plante sur des entrées négatives.

Dernière mise à jour 1 juillet 2026

Le tri par comptage est un tri sans comparaison pour des entiers dans une plage connue et limitée. Il compte combien de fois chaque valeur apparaît, puis utilise ces comptes pour écrire chaque valeur directement à sa position triée - sans aucune comparaison. Appuyez sur lecture ci-dessus pour voir les valeurs être comptées puis replacées dans l'ordre.

Le tri par comptage s'exécute en temps O(n + k), où k est la plage des valeurs d'entrée. Lorsque k n'est pas beaucoup plus grand que n, il est extrêmement rapide et peut surpasser les tris par comparaison en O(n log n), mais si la plage de valeurs est énorme, le tableau de comptage en O(k) le rend impraticable.

Complexité en temps et en espace

Cas	Complexité	Notes
Temps	O(n + k)	n éléments, k = plage de valeurs
Espace	O(n + k)	Tableau de comptage + tableau de sortie
Stable	Oui	Lorsqu'on place de droite à gauche à l'aide de sommes préfixes
Comparaison ?	Non	Trie par comptage, pas par comparaison
Idéal pour	Petite plage d'entiers	k proche de n

Étape par étape

Étape	Ce qui se passe
1	Trouver la valeur maximale pour dimensionner le tableau de comptage.
2	Compter combien de fois chaque valeur apparaît.
3	(Optionnel) Convertir les comptes en sommes préfixes pour la stabilité.
4	Écrire chaque valeur dans la sortie autant de fois qu'elle apparaît.
5	Le tableau de sortie est désormais entièrement trié.

Exemple détaillé

Tri de [1, 4, 1, 2, 4] (les valeurs vont de 0 à 4, le tableau de comptage a donc 5 cases) :

Passe	État	Action
Parcourir l'entrée	count = `[0, 2, 1, 0, 2]`	Compter les occurrences : `1` apparaît deux fois, `2` une fois, `4` deux fois.
Sommes préfixes	count = `[0, 2, 3, 3, 5]`	Chaque case contient désormais combien de valeurs sont `<=` à son indice, donnant les positions finales.
Placer `4`	output = `[_, _, _, _, 4]`	Lire de droite à gauche : `count[4] = 5`, donc `4` va à l'indice `4` ; décrémenter à `4`.
Placer `2`	output = `[_, _, 2, _, 4]`	`count[2] = 3`, donc `2` va à l'indice `2` ; décrémenter à `2`.
Placer `1`	output = `[_, 1, 2, _, 4]`	`count[1] = 2`, donc `1` va à l'indice `1` ; décrémenter à `1`.
Placer `4`	output = `[_, 1, 2, 4, 4]`	`count[4] = 4`, donc ce `4` va à l'indice `3` ; décrémenter à `3`.
Placer `1`	output = `[1, 1, 2, 4, 4]`	`count[1] = 1`, donc ce `1` va à l'indice `0`. Le tableau est trié.

Quand utiliser le tri par comptage

À utiliser quand	À éviter quand
Vous triez des entiers (ou des clés convertibles en entiers) dans une petite plage connue.	La plage de valeurs `k` est bien plus grande que le nombre d'éléments `n`.
Vous avez besoin d'un temps linéaire `O(n + k)` et pouvez vous permettre les tableaux supplémentaires.	La mémoire est limitée - le tableau de comptage coûte `O(k)` quel que soit `n`.
Vous avez besoin d'un tri stable comme sous-routine (par exemple, à l'intérieur du radix sort).	Les clés sont des flottants, des chaînes ou des objets arbitraires sans conversion en entiers.
La valeur maximale est bornée et peu coûteuse à calculer à l'avance.	La plage est inconnue ou non bornée, si bien que vous ne pouvez pas dimensionner le tableau de comptage.

Code de Counting Sort

Une implémentation propre et exécutable de Counting Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.

Code de Counting Sort en PythonPython
1def counting_sort(a):2    # Works for non-negative integers with a small max value3    counts = [0] * (max(a) + 1)4    for value in a:5        counts[value] += 16    # Prefix sums turn counts into final positions7    for i in range(1, len(counts)):8        counts[i] += counts[i - 1]9    out = [0] * len(a)10    for value in reversed(a):  # reversed keeps equal values stable11        counts[value] -= 112        out[counts[value]] = value13    return out14
15
16nums = [4, 2, 2, 8, 3, 3, 1]17print("Before:", nums)18print("After: ", counting_sort(nums))
Exécutez ce code dans le Playground Python

Code de Counting Sort en JavaScriptJavaScript
1function countingSort(arr) {2    // Count occurrences of each value, then rebuild in order3    const max = Math.max(...arr);4    const count = new Array(max + 1).fill(0);5    for (const x of arr) count[x]++;6    const out = [];7    count.forEach((c, value) => {8        for (let k = 0; k < c; k++) out.push(value);9    });10    return out;11}12
13const data = [4, 2, 9, 2, 7, 4, 1, 4];14console.log("Before:", data);15console.log("Sorted:", countingSort(data));
Exécutez ce code dans le Playground JavaScript

Code de Counting Sort en JavaJava
1import java.util.Arrays;2
3public class Main {4    static int[] countingSort(int[] arr) {5        int max = 0;6        for (int v : arr) max = Math.max(max, v);7        int[] count = new int[max + 1];8        for (int v : arr) count[v]++;9        // Prefix sums turn counts into final positions10        for (int i = 1; i <= max; i++) count[i] += count[i - 1];11        int[] out = new int[arr.length];12        // Walk backwards so equal values keep their order (stable)13        for (int i = arr.length - 1; i >= 0; i--) {14            out[--count[arr[i]]] = arr[i];15        }16        return out;17    }18
19    public static void main(String[] args) {20        int[] arr = {4, 2, 2, 8, 3, 3, 1};21        System.out.println("Before: " + Arrays.toString(arr));22        int[] sorted = countingSort(arr);23        System.out.println("After:  " + Arrays.toString(sorted));24    }25}
Exécutez ce code dans le Playground Java

Code de Counting Sort en C++C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void countingSort(std::vector<int>& a) {11    if (a.empty()) return;12    int maxVal = *std::max_element(a.begin(), a.end());13    // count[v] = how many times v appears14    std::vector<int> count(maxVal + 1, 0);15    for (int x : a) ++count[x];16    // Rebuild the array from the counts17    size_t idx = 0;18    for (int v = 0; v <= maxVal; ++v) {19        while (count[v]-- > 0) a[idx++] = v;20    }21}22
23int main() {24    std::vector<int> data = {4, 2, 2, 8, 3, 3, 1, 7};25    std::cout << "Before: ";26    printVec(data);27    countingSort(data);28    std::cout << "After:  ";29    printVec(data);30    return 0;31}
Exécutez ce code dans le Playground C++

Code de Counting Sort en CC
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void countingSort(int a[], int n) {10    int maxVal = a[0];11    for (int i = 1; i < n; i++) {12        if (a[i] > maxVal) maxVal = a[i];13    }14    // count[v] = how many times v appears15    int* count = calloc(maxVal + 1, sizeof(int));16    for (int i = 0; i < n; i++) count[a[i]]++;17    // Rebuild the array from the counts18    int idx = 0;19    for (int v = 0; v <= maxVal; v++) {20        while (count[v]-- > 0) a[idx++] = v;21    }22    free(count);23}24
25int main(void) {26    int data[] = {4, 2, 2, 8, 3, 3, 1, 7};27    int n = sizeof(data) / sizeof(data[0]);28    printf("Before: ");29    printArr(data, n);30    countingSort(data, n);31    printf("After:  ");32    printArr(data, n);33    return 0;34}
Exécutez ce code dans le Playground C

FAQ sur le tri par comptage

Quelle est la complexité temporelle du tri par comptage ?

Le tri par comptage est en O(n + k), où n est le nombre d'éléments et k la plage des valeurs possibles. Lorsque k = O(n), c'est un temps linéaire. Il utilise O(n + k) d'espace supplémentaire.

Le tri par comptage est-il stable ?

Il peut l'être. La version stable construit les sommes préfixes des comptes et place les éléments de droite à gauche, ce qui préserve l'ordre relatif des clés égales. La version simple « réécriture par valeur » montrée ici produit un tri correct mais est surtout utilisée pour des entiers simples.

Quand devrais-je utiliser le tri par comptage ?

Utilisez-le pour trier des entiers (ou des clés convertibles en entiers) dans une plage petite et connue. Si la plage de valeurs k est bien plus grande que le nombre d'éléments, le tableau de comptage gaspille de la mémoire et un tri par comparaison est préférable.

Quelle est la différence entre le tri par comptage et le tri par base (radix sort) ?

Le tri par comptage trie sur la valeur entière en une seule passe et nécessite un tableau de comptage aussi grand que la plage de valeurs. Le tri par base trie chiffre par chiffre et appelle généralement un tri par comptage stable sur chaque chiffre, ce qui maintient une petite plage par passe (par exemple 10 pour les chiffres décimaux). Le tri par base gère de grandes plages de valeurs qui rendraient un seul tri par comptage impraticable.

Pourquoi le tri par comptage n'est-il pas toujours plus rapide que le tri rapide (quicksort) ?

Le tri par comptage est en O(n + k), il ne gagne donc que lorsque la plage de valeurs k est comparable à n. Si k est énorme - par exemple trier 100 valeurs dans la plage de 0 à 1,000,000,000 - le tableau de comptage en O(k) domine et gaspille de la mémoire, tandis qu'un tri par comparaison en O(n log n) comme le quicksort reste rapide et économe en espace.

Le tri par comptage peut-il gérer les nombres négatifs ?

Oui, avec un petit décalage. Au lieu d'indexer le tableau de comptage directement par la valeur, indexez-le par value - min, de sorte que la plus petite valeur corresponde à l'indice 0. La taille du tableau de comptage devient max - min + 1. Oublier ce décalage est une erreur courante qui plante sur des entrées négatives.

Ressources associées

Plus de visualisations

Coddy programming languages illustration

Maîtrisez les algorithmes avec Coddy

COMMENCER