Tri selection

Algorithme

• rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0.
• rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1.
• continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

procédure tri_selection(t)
    n ← dernier indice de t
    pour i de 0 à n - 1
        min ← i       
        pour j de i + 1 à n
            si t[j] < t[min], alors min ← j
        fin pour
        si min ≠ i, alors échanger t[i] et t[min]
    fin pour
fin procédure

Terminaison

Aucune boucle TantQue (que des boucles Pour).

Correction

L'invariant de boucle permet de prouver la correction de l'algorithme :

• Pour tout i < n, le sous-tableau t[0:i] contient les i plus petit éléments du tableau t triés dans l'ordre croissant.
• Après l'éxécution de la boucle: t[0:i] est trié et i = n. On en déduit que le tableau t[0:n] est trié.

Complexité

• Boucle intérieure pour j de i + 1 à n

  • n - (i+1) itérations
  • une comparaison et au plus une affectation: 2 opérations élémentaires
  • (n - (i+1)) * 2 d'où une complexité O(n)

• Boucle extérieure pour i de 0 à n - 1

  • n itérations
  • 5 opérations élémentaires au plus
  • n * (5 + O(boucle intérieure))

D'où une complexité O(n²) pour le tri par séléction.