6 3 0 9 1 7 8 2 5 4

a) Tri par insertion : Nb de comparaisons

3 6 0 9 1 7 8 2 5 4   / 1
0 3 6 9 1 7 8 2 5 4   / 2
0 3 6 9 1 7 8 2 5 4   / 1
0 1 3 6 9 7 8 2 5 4   / 4
0 1 3 6 7 9 8 2 5 4   / 2
0 1 3 6 7 8 9 2 5 4   / 2
0 1 2 3 6 7 8 9 5 4   / 6
0 1 2 3 5 6 7 8 9 4   / 5
0 1 2 3 4 5 6 7 8 9   / 6
                       ----
					 = 29
					 
b) Tri shell

  On choisit un m ;
  Tant que m >= 1, 
  on trie par insertion le tableau constitué des éléments :
  [1,1+m,1+2m,...,1+km] tq 1+km <= n ;
  puis m <- m-1
  
NB : en pratique, on choisit m dans la liste (cf cours)
  et l'affectation est : m <- m / 2,3 (cf cours)
  
m = 4 :  6 1 5
6  3  0  9  1  7  8  5  4
1 3 0 9 5 7 8 2 6 4  /  3 = 1 + 2
1 3 0 9 5 7 8 2 6 4  /  1
0 1 3 9 5 7 8 2 6 4  /  2
0 1 3 9 5 7 8 2 6 4  /  1
0 1 3 5 9 7 8 2 6 4  /  2
0 1 3 5 7 9 8 2 6 4  /  2
0 1 3 5 7 8 9 2 6 4  /  2
0 1 2 3 5 7 8 9 6 4  /  6
0 1 2 3 5 6 7 8 9 4  /  4
0 1 2 3 4 5 6 7 8 9  /  6
                       ----
					 = 29       génial ! quel bon exemple !