### 1. C’est quoi une liste ?
Une liste est simplement une collection d’éléments ordonnés. Par exemple,
une liste peut être :
python
[5, 3, 8, 1, 4]
Ici, on a 5 éléments : 5, 3, 8, 1 et 4.
### 2. C’est quoi une *itération* ?
Une itération, c’est faire une action plusieurs fois. Par exemple, si on veut
regarder chaque élément de la liste un par un, on dit qu’on fait une boucle ou
des itérations.
Par exemple :
- Première itération → regarde le premier élément (ici 5)
- Deuxième itération → regarde le deuxième élément (ici 3)
- etc.
### 3. Comment fonctionne l’algorithme de tri par sélection ?
L’algorithme veut trier la liste dans l’ordre croissant (du plus petit au plus
grand). Pour cela :
- Il regarde toute la liste pour trouver le plus petit nombre.
- Il échange ce plus petit nombre avec le premier élément de la liste.
- Ensuite il regarde toute la liste sauf le premier élément (car il est déjà bien
placé) pour trouver le plus petit nombre parmi les éléments restants.
- Il échange ce nombre avec le deuxième élément.
- Et ainsi de suite jusqu’à ce que toute la liste soit triée.
### Exemple concret avec la liste [5, 3, 8, 1, 4]
- Première étape : cherche le plus petit nombre dans toute la liste → c’est 1.
- Échange ce nombre avec le premier élément (5), donc la liste devient : [1, 3, 8,
5, 4]
- Deuxième étape : cherche le plus petit nombre dans [3, 8, 5, 4] → c’est 3.
- Échange ce nombre avec le deuxième élément (qui est déjà 3), donc la liste
reste : [1, 3, 8, 5, 4]
- Troisième étape : cherche le plus petit nombre dans [8, 5, 4] → c’est 4.
- Échange ce nombre avec le troisième élément (8), la liste devient : [1, 3, 4, 5,
8]
- Et ainsi de suite...
### 4. Comment calculer les opérations ?
Pour chaque étape :
- Tu regardes tous les éléments restants pour trouver le minimum.
- Le nombre d’éléments que tu regardes diminue à chaque fois.
Si ta liste a n éléments :
| Étape | Nombre d’éléments à regarder |
|-------|------------------------------|
|1 |n-1 |
|2 |n-2 |
|3 |n-3 |
|... | ... |
|n -1 | 1 |
Pour calculer combien ça fait au total :
On additionne ces nombres :
\[
(n -1) + (n -2) + (n -3) + ... + 1 = \frac{n(n-1)}{2}
\]
C’est une formule mathématique connue qui donne la somme des nombres
entiers de \(1\) à \(n-1\).
### Ce que ça signifie
Quand on dit que l’algorithme fait environ \(\frac{n(n-1)}{2}\) comparaisons :
- Ça veut dire qu’il regarde environ autant d’éléments que cette somme pour
trouver les minimums successifs.
En gros :
- Si tu as une petite liste (par exemple n=5), tu fais peu d’opérations.
- Si ta liste est très grande (par exemple n=1000), tu fais beaucoup plus
d’opérations — ça grandit comme \(n^2\).
### Conclusion simple
- La liste est juste un groupe d’éléments à trier.
- Une itération est un passage où tu regardes ou manipules des éléments.
- Le calcul des opérations se fait en additionnant tous les éléments que tu
regardes à chaque étape.