Tri par paquets

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 Lk est associé à l'intervalle Ik = [a + k(b − a) / n,a + (k + 1)(b − a) / n[.
  • Pour chaque élément T[i] :
  • Trier chaque liste Lk, 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 : Θ(n2) 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(n2)[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 (2e édition), Dunod 2004. (ISBN 2-10-003922-9). (section 8.4, p. 169)
v · Algorithmes de tri

à bulle • par sélection • par insertion • par tas • par base • par paquets • rapide • smoothsort • fusion • comptage • de Shell

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tri par paquets de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Tri par insertion — Exemple du tri par insertion utilisant une liste de nombres aléatoires Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C est le tri que la plupart des personnes utilisent naturellement pour trier des… …   Wikipédia en Français

  • Tri par base — Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base… …   Wikipédia en Français

  • Tri par sélection — Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s exécute en temps quadratique en le nombre d éléments à trier. Sommaire 1… …   Wikipédia en Français

  • Tri par tas — Une exécution de l algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l …   Wikipédia en Français

  • Tri stable — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

  • Tri fusion — appliqué à un tableau de 7 éléments. Le tri fusion est un algorithme de tri stable par comparaison. Sa complexité temporelle pour une entrée de taille n est de l ordre de n log n, ce qui est asymptotiquement optimal. Le tri fusion se décrit… …   Wikipédia en Français

  • Tri rapide — Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961[1] et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes.… …   Wikipédia en Français

  • Tri à bulles — Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d un tableau, comme les bulles d air… …   Wikipédia en Français

  • Tri de Shell — Le tri de Shell ou Shell Sort en anglais est un algorithme de tri. C est une amélioration notable du tri par insertion au niveau de la vitesse d exécution mais ce tri n est pas stable. Il est facile de comprendre intuitivement comment fonctionne… …   Wikipédia en Français

  • Tri comptage — Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s applique sur des valeurs entières. Définition Le principe repose sur la construction de l histogramme des données, puis le balayage de celui ci de façon croissante, afin de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”