Tri par paquets

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

Dans le pire cas, les ${\displaystyle 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é en temps dans le pire cas est égale à la complexité dans le pire cas de l'algorithme auxiliaire, par exemple ${\displaystyle \Theta (n^{2})}$ avec un tri par insertion et ${\displaystyle \Theta (n\log n)}$ avec un 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, que l'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).