Tri comptage

Le tri par comptage ordonne les valeurs entières en comptant le nombre d’occurrences de chacune, puis en utilisant ces fréquences pour placer les valeurs dans l’ordre trié. Il évite les comparaisons deux à deux, mais son temps d’exécution et sa consommation mémoire dépendent de l’étendue des valeurs. Il est utile lorsque cette étendue est assez réduite ; une plage clairsemée peut le rendre impraticable. Il sert également de sous-programme au tri par base. Sa borne de complexité principale est O(n + k), où n désigne le nombre de valeurs et k la largeur de la plage.

Fonctionnement du tri par comptage

Supposons que l’entrée contienne n entiers. Trouvez son minimum min et son maximum max, puis allouez k = max - min + 1 compteurs. Le décalage min permet à l’algorithme de représenter les valeurs négatives par des indices de compteur non négatifs :

Pour une plage allant de la valeur minimale à la valeur maximale, associez chaque valeur x à l’indice de compteur x - min.

Pour chaque valeur d’entrée x, incrémentez count[x - min]. Ces compteurs représentent les fréquences : l’indice i correspond à la valeur min + i. Transformez les fréquences en positions cumulées en ajoutant chaque compteur à celui qui le précède. Après cette étape, chaque compteur indique le nombre de valeurs d’entrée inférieures ou égales à la valeur qu’il représente ; il donne ainsi la position finale, en commençant à un, de la dernière occurrence de cette valeur.

Pour construire un résultat stable lorsque les éléments sont des enregistrements dotés de clés, parcourez l’entrée de droite à gauche. Placez chaque enregistrement à l’indice count[key - min] - 1, puis décrémentez ce compteur. Le parcours en sens inverse préserve l’ordre initial des enregistrements qui ont la même clé :

Lors du tri d’enregistrements selon une clé, parcourez l’entrée de droite à gauche pendant le placement afin que les enregistrements de même clé conservent leur ordre initial.

Une entrée vide ne nécessite aucun compteur : renvoyez un résultat vide avant de rechercher un minimum ou un maximum. Une implémentation de base pour les entiers conserve les valeurs ; pour trier des enregistrements, il faut placer chaque enregistrement dans le tableau de sortie pendant le placement.

Exemple détaillé : trier des valeurs avec le tri par comptage

Considérons l’entrée (6, 3, 2, 7, 4, 5, 4, 2). Son minimum est 2, son maximum est 7 et la largeur de la plage vaut k = 7 - 2 + 1 = 6. Les indices de compteur 0 à 5 représentent les valeurs 2 à 7.

Par exemple, count[4 - 2] vaut 2 : la valeur 4 apparaît donc deux fois. Après le cumul, le compteur de 4 vaut 5 : le dernier 4 doit occuper l’indice 4 du tableau de sortie, en commençant à zéro. En décrémentant cette position, on réserve la case précédente à l’autre 4. En répétant ce placement pour les valeurs restantes, on obtient (2, 2, 3, 4, 4, 5, 6, 7).

Le diagramme ci-dessous utilise des étiquettes distinctes pour montrer comment le décalage, les fréquences, les positions cumulées et le placement en sens inverse s’articulent. Son exemple comprend une clé négative et montre que les enregistrements ayant la même clé conservent leur ordre initial.

Diagramme : la plage de -1 à 4 correspond à six indices de compteur ; les fréquences deviennent des positions cumulées, et le placement en sens inverse conserve (4,A) avant (4,C) dans le résultat.

Implémenter le tri par comptage en C++

Cet exemple complet en C++ renvoie un nouveau vecteur, prend en charge les entiers signés grâce à l’indexation avec décalage et traite un vecteur vide avant de rechercher ses bornes. Il utilise des conteneurs standard plutôt que des tableaux de longueur variable.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<int> countingSort(const std::vector<int>& values) {
    if (values.size() == 0) {
        return {};
    }

    const auto bounds = std::minmax_element(values.begin(), values.end());
    const long long minValue = *bounds.first;
    const long long maxValue = *bounds.second;
    const std::size_t range = static_cast<std::size_t>(maxValue - minValue + 1);
    std::vector<std::size_t> count(range, 0);

    for (int value : values) {
        const std::size_t index = static_cast<std::size_t>(value - minValue);
        ++count[index];
    }

    for (std::size_t i = 1; i < count.size(); ++i) {
        count[i] += count[i - 1];
    }

    std::vector<int> output(values.size());
    for (std::size_t i = values.size(); i-- > 0;) {
        const int value = values[i];
        const std::size_t index = static_cast<std::size_t>(value - minValue);
        output[--count[index]] = value;
    }
    return output;
}

int main() {
    const std::vector<int> input{6, 3, 2, 7, 4, 5, 4, 2};
    const std::vector<int> sorted = countingSort(input);

    std::cout << "Input: ";
    for (int value : input) {
        std::cout << value << ' ';
    }
    std::cout << "\nSorted: ";
    for (int value : sorted) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

L’exemple affiche l’entrée puis les valeurs triées lorsqu’il est compilé et exécuté. Les libellés Input: et Sorted: affichés par le code inchangé restent en anglais. Cette implémentation trie des entiers ; pour trier des enregistrements de manière stable, placez l’enregistrement complet dans output à la position calculée, au lieu d’y stocker uniquement sa clé.

Complexité et choix du tri par comptage

La recherche de la plage, le comptage des valeurs, le cumul des positions et le placement des valeurs prennent chacun un temps linéaire par rapport à la taille de l’entrée ou de la plage concernée. Le temps total est O(n + k). L’espace auxiliaire est également O(n + k) pour les compteurs et le vecteur de sortie. Ici, k = max - min + 1 : le coût dépend donc de l’écart entre la valeur minimale et la valeur maximale, et pas seulement du nombre de valeurs présentes.

Utilisez le tri par comptage lorsque les valeurs sont des entiers et que la plage est assez petite pour accueillir k compteurs et une sortie de n éléments. Par exemple, il peut convenir à un grand ensemble de notes comprises dans une plage fixe réduite. Une petite entrée répartie sur une plage immense peut exiger trop de mémoire et de temps d’initialisation, même si la plupart des valeurs ne se présentent jamais ; un tri par comparaison ou un tri par base peut alors être préférable. Le vecteur de compteurs doit tenir dans la mémoire disponible : estimez donc la largeur de la plage avant de l’allouer.