Tri par insertion
Principe
Le principe est simple, on va suposer que l'on a un tableau qui est partielment trié, c'est à dire que les X premières cases du tableau sont triés (au debut la première case est trié avec elle même...). Ensuite on prendra le premier élément non trié et on va l'insérer à sa place dans la partie trié. On continue tant qu'il y a des éléments à trié.
Algorithme
algo tri_par_insertion (T) parametre: T[0...N]: tableau d'entier(E/S) variable: i, j, k, at: entier DEBUT i<-1 tantque i!=N at<-T[i+1] j<-1 tantque j<i+1 ET T[j]<at j<-j+1 Rq: dans j on a la position ou mettre at k<-i tantque k!=j T[k+1]<-T[k] k<-k+1 Rq: on a juste deplacer les i-j dernieres cases du tableau t[j]<-at i<-i+1 FIN
Complexite
Worst case: O(N2) car on a deux boucles imbriquées qui potentielment peuvent parcourrir la totalité du tableau. On peut améliorer un peu le tri en cherchant j à l'envers ce qui ferait que si at est déjà à la bonne place on passerait directement à la case suivante. Etant donné que l'on accède au élément à partir d'élément voisin (l'élément précédant ou l'élément suivant), l'utilisation d'une liste chaine pourait accélerer les performances de ce tri. On aurait ainsi pas à décaler les i-j dernières valeurs.