Les quatre tris à la main

Les déroulements ci-dessous sont produits par le programme TracesTris.java.

• Tri par insertion : $T[k]$ est inséré dans $T[0:k]$, déjà trié.

  k=1 (insere 7) : [4, 7, 1, 3, 8, 2, 6, 5]
  k=2 (insere 1) : [1, 4, 7, 3, 8, 2, 6, 5]
  k=3 (insere 3) : [1, 3, 4, 7, 8, 2, 6, 5]
  k=4 (insere 8) : [1, 3, 4, 7, 8, 2, 6, 5]
  k=5 (insere 2) : [1, 2, 3, 4, 7, 8, 6, 5]
  k=6 (insere 6) : [1, 2, 3, 4, 6, 7, 8, 5]
  k=7 (insere 5) : [1, 2, 3, 4, 5, 6, 7, 8]

nom : T
valeurs : 1 3 4 7 8 2 6 5
vert : 0..4
colorier : 5
pointeurs : k=5
fleches : 5->1
fleches-bas : 1->2 2->3 3->4 4->5
legende : k = 5 : T[0:5] est trié ; 2 va en case 1, 3 4 7 8 glissent à droite

• Tri par fusion : les fusions se font dans l'ordre des retours d'appels, de la gauche vers la droite.

  fusion de [0:1) et [1:2) : [4, 7, 1, 3, 8, 2, 6, 5]
  fusion de [2:3) et [3:4) : [4, 7, 1, 3, 8, 2, 6, 5]
  fusion de [0:2) et [2:4) : [1, 3, 4, 7, 8, 2, 6, 5]
  fusion de [4:5) et [5:6) : [1, 3, 4, 7, 2, 8, 6, 5]
  fusion de [6:7) et [7:8) : [1, 3, 4, 7, 2, 8, 5, 6]
  fusion de [4:6) et [6:8) : [1, 3, 4, 7, 2, 5, 6, 8]
  fusion de [0:4) et [4:8) : [1, 2, 3, 4, 5, 6, 7, 8]

• Tri rapide : chaque segmentation place définitivement un pivot.

  segmenter [0:8) pivot 5 -> case 4 : [4, 1, 3, 2, 5, 7, 6, 8]
  segmenter [0:4) pivot 2 -> case 1 : [1, 2, 3, 4, 5, 7, 6, 8]
  segmenter [2:4) pivot 4 -> case 3 : [1, 2, 3, 4, 5, 7, 6, 8]
  segmenter [5:8) pivot 8 -> case 7 : [1, 2, 3, 4, 5, 7, 6, 8]
  segmenter [5:7) pivot 6 -> case 5 : [1, 2, 3, 4, 5, 6, 7, 8]

Les zones de taille $1$ ($[0:1]$, $[2:3]$, $[6:7]$) et vides ne sont pas segmentées.

nom : T
valeurs : 4 1 3 2 5 7 6 8
colorier : 4
zone : 0..3 au plus 5
zone : 5..7 > 5
legende : première segmentation : le pivot 5 est à sa place définitive

• Tri par tas : on entasse les cases $3,2,1,0$, puis on échange la racine avec la dernière case du tas et on entasse la racine.

  tas construit : [8, 7, 6, 5, 4, 2, 1, 3]
  extraction de 8 : [7, 5, 6, 3, 4, 2, 1, 8]
  extraction de 7 : [6, 5, 2, 3, 4, 1, 7, 8]
  extraction de 6 : [5, 4, 2, 3, 1, 6, 7, 8]
  extraction de 5 : [4, 3, 2, 1, 5, 6, 7, 8]
  extraction de 4 : [3, 1, 2, 4, 5, 6, 7, 8]
  extraction de 3 : [2, 1, 3, 4, 5, 6, 7, 8]
  extraction de 2 : [1, 2, 3, 4, 5, 6, 7, 8]

On vérifie le tas construit : chaque case $i$ est supérieure ou égale à ses fils $2i+1$ et $2i+2$ ($8\ge 7,6$ ; $7\ge 5,4$ ; $6\ge 2,1$ ; $5\ge 3$).

nom : T
valeurs : 8 7 6 5 4 2 1 3
fleches : 0->1 1->3 2->5 3->7
fleches-bas : 0->2 1->4 2->6
legende : tas construit : du père i vers ses fils 2i+1 (dessus), 2i+2 (dessous)