Retour

Tri par insertion

Principe

Le tri par sélection consiste à chaque étape à rechercher le plus petit élément non encore trié et à le placer à la suite des éléments déjà triés.

Algorithme impératif

Text Only

VARIABLES
t : tableau d'entiers
i, j, k : nombre entier

TRI_INSERTION(t):
  DEBUT
  j←2
  TANT QUE j<= longueur(t):  //boucle 1
    i←j-1
    k←t[j]
    TANT QUE i>0 et t[i]>k:   //boucle 2
      t[i+1]←t[i]
      i←i-1
    FIN TANT QUE
    t[i+1]←k
    j←j+1
  FIN TANT QUE
  FIN 

Implémentation en Python

🐍 Script Python

def Tri_Insertion(t):
  j = 1
  while j < len(t):
    i = j - 1
    k = t[j]
    while i >= 0 and t[i] > k:
      t[i+1] = t[i]
      i = i - 1
    t[i+1] = k
    j = j + 1

Complexité

Pire cas : Quadratique	$$ O(n^2) $$
Moyenne : Quadratique	$$ O(n^2) $$
Meilleur cas : Linéaire	$$ O(1) $$