Tri par paquets

Le tri par paquets est un algorithme de tri fondé sur la distribution, et non un tri par comparaison. Il répartit les valeurs dans des paquets ordonnés, trie les valeurs de chaque paquet, puis rassemble les paquets dans l’ordre pour produire le résultat. Il est particulièrement efficace lorsque les valeurs sont réparties assez uniformément dans un intervalle connu. Cette approche de répartition et de rassemblement est utile lorsqu’on dispose d’une correspondance adaptée entre les valeurs et les paquets.

Algorithme de tri par paquets

Choisissez k paquets couvrant l’intervalle des valeurs, puis affectez chaque valeur au paquet correspondant à son intervalle. Pour les valeurs de [0, 1), une règle pratique à partir de zéro est floor(k * x) : le paquet j couvre [j/k, (j+1)/k). La borne supérieure est exclue ; chaque valeur admise correspond donc à un indice compris entre 0 et k - 1. Les valeurs en dehors de cet intervalle doivent être normalisées ou traitées avec une autre correspondance : cette formule n’est pas universelle.

Voici les étapes :

1. Créez k paquets pour l’intervalle choisi.
2. Parcourez chaque valeur d’entrée x et placez-la dans le paquet floor(k * x).
3. Triez chaque paquet séparément. Le tri par insertion est souvent utilisé pour les petits paquets, mais d’autres méthodes de tri locales conviennent aussi.
4. Parcourez les paquets dans l’ordre de leurs indices et ajoutez leurs valeurs triées au résultat.

La correspondance entre les valeurs et les paquets préserve l’ordre d’un paquet à l’autre : toute valeur du paquet j est inférieure à toute valeur du paquet j + 1. Le tri à l’intérieur de chaque paquet ordonne les valeurs qui appartiennent au même intervalle. L’article sur le tri par insertion cité plus haut présente une méthode locale simple ; l’implémentation ci-dessous utilise plutôt la fonction sort de la bibliothèque standard C++.

Exemple de tri par paquets

Prenons dix intervalles de même taille sur [0, 1) ; l’indice se calcule alors avec floor(10 * x). Les intervalles sont [0.0, 0.1), [0.1, 0.2), et ainsi de suite jusqu’à [0.9, 1.0). En particulier, 0.1 va dans le paquet 1, car l’extrémité gauche appartient à cet intervalle.

Pour l’entrée (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31), la répartition donne :

Après le tri de chaque paquet, le paquet 2 contient 0.21, 0.22 et le paquet 3 contient 0.31, 0.33, 0.38 ; chacun des autres paquets non vides ne contient qu’une valeur. En concaténant les paquets de 0 à 9, on obtient (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55) en ordre croissant.

Implémentation de l’algorithme de tri par paquets

Ce programme C++ utilise les huit mêmes valeurs que l’exemple précédent. Il les répartit dans dix paquets, trie chaque paquet, puis affiche la séquence rassemblée.

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

std::vector<double> bucketSort(const std::vector<double>& values,
                               std::size_t bucketCount) {
    std::vector<std::vector<double>> buckets(bucketCount);

    for (double value : values) {
        const std::size_t index = static_cast<std::size_t>(value * bucketCount);
        buckets[index].push_back(value);
    }

    std::vector<double> result;
    result.reserve(values.size());
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }
    return result;
}

int main() {
    const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
                                        0.38, 0.55, 0.21, 0.31};
    const std::vector<double> sorted = bucketSort(values, 10);

    std::cout << "Sorted values:";
    for (double value : sorted) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}

Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55

La fonction suppose que bucketCount est strictement positif et que chaque valeur appartient à [0, 1), ce qui garantit que l’indice calculé reste dans les limites du vecteur de paquets. Pour un autre intervalle, normalisez les valeurs ou définissez une correspondance adaptée avant de calculer les indices. Les éléments de code et de sortie sont conservés à l’identique ; le libellé affiché par le programme reste donc en anglais. Les éléments d’exécution fournis indiquent que ce programme a été exécuté avec succès, avec un code de sortie 0 et la séquence triée présentée plus haut.

Complexité de l’algorithme de tri par paquets

Soit n le nombre de valeurs, k le nombre de paquets et b_j le nombre de valeurs dans le paquet j. La création des paquets et la répartition des valeurs prennent O(n + k). Si chaque paquet est trié par comparaison, par exemple avec std::sort, le travail supplémentaire est borné par la somme des coûts de tri locaux, soit O(Σ b_j log b_j) ; un seul paquet très rempli peut donc porter le temps total à O(n log n). Un temps attendu proche du linéaire est possible lorsque les valeurs sont réparties de sorte que les paquets restent peu remplis, généralement avec k proportionnel à n et une distribution d’entrée à peu près uniforme. Le nom de l’algorithme ne garantit pas à lui seul ce résultat.

Si le tri par insertion est utilisé dans les paquets, un paquet de taille b_j peut nécessiter O(b_j²) dans le pire cas. Un paquet très rempli peut alors porter le temps total à une complexité quadratique. Le choix de la méthode de tri locale et la distribution des valeurs doivent donc tous deux être pris en compte pour estimer les performances.

L’espace auxiliaire est O(n + k) : les paquets contiennent les n valeurs, et leur structure comporte k entrées. C’est l’espace utilisé par l’implémentation, qui renvoie un vecteur trié distinct. La complexité n’est pas O(n * k), car chaque valeur est rangée dans un seul paquet au lieu d’être copiée dans tous les paquets.