Tri par paquets

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Tri par paquets

Problèmes liés	Algorithme, algorithme de tri
Structure des données	Tableau
Basé sur	Pigeonhole sort (en)

Complexité en temps

Pire cas	${\displaystyle O(n^{2})}$

Complexité en espace

Pire cas	${\displaystyle O(n\cdot k)}$
Moyenne	${\displaystyle O(n+{\frac {n^{2}}{k}}+k)}$

modifier - modifier le code - modifier Wikidata

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 à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors 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é temporelle moyenne du tri par paquets est linéaire, et ce quel que soit 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 ${\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}}$.

Complexité

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 O(n^{2})}$ avec un tri par insertion et ${\displaystyle O(n\log \cdot 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 ${\displaystyle O(1)}$, et ce, que l'on utilise un algorithme de tri en ${\displaystyle O(n\cdot \log n)}$ ou ${\displaystyle O(n^{2})}$^[1]. Par conséquent, la complexité en moyenne de l'algorithme complet est ${\displaystyle O(n)}$.

Notes et références

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l'informatique théorique