Tri par insertion

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 cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.

En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique.

Le tri par insertion est cependant considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide (ou quicksort).

En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin.

Sommaire

Description de l'algorithme

Dans l'algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-ème élément, les éléments qui le précèdent sont déjà triés. Pour faire l'analogie avec l'exemple du jeu de cartes, lorsqu'on est à la i-ème étape du parcours, le i-ème élément est la carte saisie, les éléments précédents sont la main triée et les éléments suivants correspondent aux cartes encore mélangées sur la table.

L'objectif d'une étape est d'insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion. En pratique, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à rencontrer un élément plus petit.

Voici une description en pseudo-code de l'algorithme présenté. Les éléments du tableau T sont numérotés de 0 à n-1.

  procédure tri_insertion(tableau T, entier n)
      pour i de 1 à n - 1
          x := T[i]
          j := i
          tant que j > 0 et T[j - 1] > x
              T[j] := T[j - 1]
              j := j - 1;
          T[j] := x

Le tri par insertion est un tri stable (conservant l'ordre d'apparition des éléments égaux) et un tri en place (il n'utilise pas de tableau auxiliaire).

Exemple

Voici les étapes de l'exécution du tri par insertion sur le tableau T = [9,6,1,4,8]. Le tableau est représenté au début et à la fin de chaque itération.

i = 1
9 6 1 4 8
\rightarrow
6 9 1 4 8
i = 2
6 9 1 4 8
\rightarrow
1 6 9 4 8
i = 3
1 6 9 4 8
\rightarrow
1 4 6 9 8
i = 4
1 4 6 9 8
\rightarrow
1 4 6 8 9

Complexité

La complexité du tri par insertion est Θ(n2) dans le pire cas et en moyenne, et linéaire dans le meilleur cas. Plus précisément :

  1. Dans le pire cas, atteint lorsque le tableau est trié à l'envers, l'algorithme effectue de l'ordre de n2/2 affectations et comparaisons[1].
  2. Si les éléments sont distincts et que toutes leurs permutations sont équiprobables, alors en moyenne, l'algorithme effectue de l'ordre de n2/4 affectations et comparaisons[1].
  3. Si le tableau est déjà trié, il y a n-1 comparaisons et O(n) affectations.

La complexité du tri par insertion reste linéaire si le tableau est presque trié (par exemple, chaque élément est à une distance bornée de la position où il devrait être, ou bien tous les éléments sauf un nombre borné sont à leur place). Dans cette situation particulière, le tri par insertion surpasse d'autres méthodes de tri : par exemple, le tri fusion et le tri rapide (avec choix aléatoire du pivot) sont tous les deux en \Theta(n\,\log n) même sur une liste triée.

Variantes et optimisations

Optimisations pour les tableaux

Plusieurs modifications de l'algorithme permettent de diminuer le temps d'exécution, bien que la complexité reste quadratique.

  • On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés. Il est possible d'implémenter cette variante de sorte que le tri soit encore stable.
  • En utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément, on peut ne faire que O(n\,\log n) comparaisons. Le nombre d'affectations reste en O(n2).
  • L'insertion d'un élément peut être effectuée par une série d'échanges plutôt que d'affectations. En pratique, cette variante peut être utile dans certains langages de programmation (par exemple C++), où l'échange de structures de données complexes est optimisé, alors que l'affectation provoque l'appel d'un constructeur de copie (en).

Le tri de Shell est une variante du tri par insertion qui améliore sa complexité asymptotique, mais n'est pas stable.

Tri par insertion sur des listes

Le principe du tri par insertion peut être adapté à des listes chaînées. Dans ce cas, le déplacement de chaque élément peut se faire en temps constant (une suppression et un ajout dans la liste). Par contre, le nombre de comparaisons nécessaires pour trouver l'emplacement où insérer reste de l'ordre de n²/4, la méthode de recherche par dichotomie ne pouvant pas être appliquée à des listes.

Combinaison avec d'autres tris

En pratique, les algorithmes de tri en O(n\,\log n) basés sur la méthode « diviser pour régner » (tri fusion, tri rapide) sont moins efficaces que le tri par insertion sur les petites entrées, en dessous d'une taille critique K (qui dépend de l'implémentation et de la machine utilisée). Dans ce type d'algorithmes, plutôt que de diviser récursivement l'entrée jusqu'à avoir des sous-problèmes élémentaires de taille 1 ou 2, on peut s'arrêter dès que les sous-problèmes ont une taille inférieure à K et les traiter avec le tri par insertion.

Pour le cas particulier du tri rapide, une variante plus efficace existe[2] :

  • exécuter d'abord le tri rapide en ignorant simplement les sous-problèmes de taille inférieure à K ;
  • faire un tri par insertion sur le tableau complet à la fin, ce qui est rapide car la liste est déjà presque triée.

Voir aussi

Notes et références

  1. ↑ a et b (en) Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley 1973 (ISBN 978-0-201-03803-3). (section 5.2.1, p. 83)
  2. ↑ (fr) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique (2e édition), Dunod 2004. (ISBN 978-2-10-003922-7). (ex. 7.4.5, p. 153)
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 insertion de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Tri par selection — Tri par sélection Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l on va replacer à sa position finale c est à dire en… …   Wikipédia en Français

  • 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 …   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 par dénombrement — Tri comptage Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s applique sur des valeurs entières. Sommaire 1 Définition 2 Exemple 3 Algorithme 4 Implémentation …   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 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 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 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 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

Share the article and excerpts

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