Tri par paquets

Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l'avance.

Le principe de ce tri consiste à diviser l'intervalle d'entrée en petits sous-intervalles identiques et à répartir les données en paquets, chaque paquet correspondant à un de ces sous-intervalles. Après cette opération, les paquets sont triés séparément à l'aide d'un autre algorithme de tri.

Si les nombres en entrée sont uniformément distribués dans l'intervalle initial, alors la complexité moyenne du tri par paquets est linéaire, indépendamment de l'algorithme de tri auxiliaire utilisé.

Description de l'algorithme

Le tri par paquets prend en entrée un tableau T de n nombres réels appartenant à un intervalle [a, b[. Le déroulement de l'algorithme est le suivant :

• Créer n listes $L_0,\dots,L_{n-1}$ appelées paquets. Le paquet L_k est associé à l'intervalle I_k = [a + k(b − a) / n,a + (k + 1)(b − a) / n[.
• Pour chaque élément T[i] :
  • Calculer l'intervalle I_k dans lequel il se trouve : $k=\lfloor n (T[i]-a)/(b-a) \rfloor$, où la notation $\lfloor \cdot \rfloor$ désigne la partie entière inférieure.
  • Ajouter T[i] à L_k.
• Trier chaque liste L_k, par exemple avec un tri par insertion.
• Renvoyer la concaténation des listes $L_0,\dots,L_{n-1}$.

Complexité

Dans le pire cas, les n nombres de l'entrée se trouvent dans le même sous-intervalle et sont tous placés dans le même paquet. Ainsi, la complexité dans le pire cas est égale à la complexité dans le pire cas de l'algorithme auxiliaire : Θ(n²) avec le tri par insertion, ou Θ(n log n) avec par exemple le tri fusion.

Comme il y a autant de paquets que de nombres, la taille moyenne de chaque paquet est 1. En utilisant l'hypothèse de distribution uniforme, on peut aussi démontrer que le temps moyen pour trier un paquet est O(1), et ce qu'on utilise un algorithme de tri en O(n log n) ou O(n²)^[1]. Par conséquent, la complexité en moyenne de l'algorithme complet est Θ(n).

Notes et références

1. ↑ (fr) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique (2^e édition), Dunod 2004. (ISBN 2-10-003922-9). (section 8.4, p. 169)