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.

Tri par paquets
Problèmes liés
Structure des données
Basé sur
Pigeonhole sort (en)
Complexité en temps
Pire cas
Complexité en espace
Pire cas
Moyenne

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 appelées paquets. Le paquet est associé à l'intervalle .
  • Pour chaque élément T[i] :
    • Calculer l'intervalle dans lequel il se trouve : , où la notation désigne la partie entière inférieure.
    • Ajouter T[i] à .
  • Trier chaque liste , par exemple avec un tri par insertion.
  • Renvoyer la concaténation des listes .

Complexité

Dans le pire cas, les 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 avec un tri par insertion et 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(n2)[1]. Par conséquent, la complexité en moyenne de l'algorithme complet est Θ(n).

Notes et références

  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.