Dérouler la recherche du $k$-ème élément

Le programme Tableaux.java affiche, tour par tour :

  zone [0:8) -> pivot 5 en case 3, T = [1, 3, 2, 5, 9, 8, 7, 6]
  zone [4:8) -> pivot 6 en case 4, T = [1, 3, 2, 5, 6, 8, 7, 9]
  zone [5:8) -> pivot 9 en case 7, T = [1, 3, 2, 5, 6, 8, 7, 9]
  zone [5:7) -> pivot 7 en case 5, T = [1, 3, 2, 5, 6, 7, 8, 9]
  resultat 7

• Tour 1 : le pivot $5$ arrive en case $3<5$ ; la valeur cherchée est à droite : $g=4$.
• Tour 2 : le pivot $6$ arrive en case $4<5$ : $g=5$.
• Tour 3 : le pivot $9$ arrive en case $7>5$ : $d=7$.
• Tour 4 : le pivot $7$ arrive en case $5=k$ : on retourne $7$.

nom : T
valeurs : 1 3 2 5 9 8 7 6
griser : 0..2
colorier : 3
pointeurs : p=3 k=5
legende : tour 1 : pivot 5 en case 3 < 5, la zone devient T[4:8]

nom : T
valeurs : 1 3 2 5 6 8 7 9
griser : 0..3
colorier : 4 7
pointeurs : g=5 k=5 d=7
legende : tours 2 et 3 : pivots 6 en case 4 et 9 en case 7, zone T[5:7]

nom : T
valeurs : 1 3 2 5 6 7 8 9
griser : 0..4 6..7
vert : 5
pointeurs : p=5 k=5
legende : tour 4 : pivot 7 en case 5 = k, on retourne 7

Le tableau trié est $[1,2,3,5,6,7,8,9]$ : sa case $5$ contient bien $7$. Les cases $0$ à $2$ ne sont pas triées à la fin ($[1,3,2]$) : la recherche n'a jamais eu besoin de les ordonner, c'est ce qui la rend plus rapide qu'un tri.