📝 Fiche de révision — Algorithmes sur les tableaux : parcours et tris

🔍 Parcours séquentiel

def recherche(t, v):
    for i in range(len(t)):
        if t[i] == v:
            return i
    return -1

• Maximum : m = t[0] puis for i in range(1, len(t)): if t[i] > m: m = t[i] ; moyenne : somme / len(t).
• Valeurs de type quelconque ; arrêt à la première occurrence.
• Coût linéaire : $n$ comparaisons au pire (absent ou dernier) ; $n \times 10 \Rightarrow$ temps $\times 10$.

🔽 Tri par sélection

for i in range(n - 1):
    i_min = i
    for j in range(i + 1, n):
        if t[j] < t[i_min]:
            i_min = j
    t[i], t[i_min] = t[i_min], t[i]

• Invariant : au début de l'étape $i$, t[0..i-1] trié et $\leq$ tout t[i..n-1].
• Initialisation (vide) → conservation (le minimum placé en t[i]) → conclusion (trié).
• Coût : $(n-1) + \cdots + 1 = n(n-1)/2$ comparaisons toujours ; au plus $n - 1$ échanges.
• Terminaison : boucles for bornées.

➡️ Tri par insertion

for i in range(1, n):
    x = t[i]
    j = i - 1
    while j >= 0 and t[j] > x:
        t[j + 1] = t[j]
        j = j - 1
    t[j + 1] = x

• Invariant : au début de l'étape $i$, t[0..i-1] trié (mêmes éléments).
• Terminaison du while : variant j décroît de 1, s'arrête à $-1$.
• Coût : déjà trié $n - 1$ comparaisons ; inversé $n(n-1)/2$ comparaisons et décalages ; quadratique au pire.
• j >= 0 and t[j] > x : évaluation séquentielle protège t[-1].

📈 Coûts

• $n = 100$ : $4\,950$ ; $n = 10^6$ : $5 \times 10^{11}$ : impraticable → tris en $n \log n$ (terminale, sorted).

🧾 Rédiger une preuve

1. Invariant énoncé précisément (indices).
2. Initialisation : vrai avant le premier tour.
3. Conservation : vrai avant → vrai après un tour.
4. Conclusion : à la sortie, la propriété donne le résultat.
5. Terminaison : for borné ; while : variant entier strictement décroissant minoré.

⚠️ Pièges à éviter

📌 À retenir

1. Parcours : linéaire.
2. Sélection : minimum + échange, $n(n-1)/2$.
3. Insertion : décalages, $n-1$ à $n(n-1)/2$.
4. Invariant = preuve de correction.
5. Variant = preuve de terminaison.