NSI · Première · Algorithmique et programmation
Algorithmes sur les tableaux
Chercher, trier, et prouver que ça marche.
En bref
Quatre algorithmes de base reviennent partout : il faut savoir les écrire, les prouver et les évaluer.
Les deux recherches
| La recherche | Sa condition | Son coût (pire cas) | Sur un million d'éléments |
|---|---|---|---|
| Séquentielle | Aucune | Linéaire : n comparaisons | Un million de comparaisons |
| Dichotomique | Le tableau doit être trié | Logarithmique | Une vingtaine |
La dichotomie compare l'élément cherché à celui du milieu et élimine la moitié où il ne peut pas se trouver.
La condition « trié » n'est pas un détail : appliquée à un tableau non trié, la dichotomie rend un résultat faux sans le signaler.
Son variant est la taille de l'intervalle de recherche, divisée par deux à chaque tour : c'est ce qui prouve la terminaison.
Le calcul d'un extremum
| L'étape | Ce qu'on fait |
|---|---|
| 1 | Mémoriser le premier élément comme candidat |
| 2 | Parcourir, en remplaçant le candidat dès qu'on trouve mieux |
Coût linéaire, un seul parcours.
Chercher le maximum puis le minimum en deux parcours est un gaspillage évitable.
L'invariant s'énonce simplement : après i tours, le candidat est le maximum des i premiers éléments.
Les tris
| Le tri | Son principe | Son point fort |
|---|---|---|
| Par sélection | Chercher le plus petit du reste et le placer à sa position finale, n fois | Un nombre d'échanges minimal |
| Par insertion | Insérer chaque élément à sa place dans la partie déjà triée, comme on trie des cartes en main | Quasi linéaire sur un tableau presque trié |
Tous deux sont quadratiques dans le pire cas.
Pourquoi n log n change tout
| L'algorithme | Sur un million d'éléments |
|---|---|
| En n log n (bibliothèques) | Une seconde |
| En n² | Plusieurs jours |
C'est l'écart qui justifie de connaître la complexité avant d'écrire le code.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quelle condition la recherche dichotomique exige-t-elle ?
2.Quel est le coût de la recherche séquentielle dans le pire cas ?
3.Combien de comparaisons environ pour une dichotomie sur un million d’éléments ?
4.Quel est le variant de boucle de la recherche dichotomique ?
5.Le tri par insertion et le tri par sélection sont tous deux quadratiques dans le pire cas.
6.Comment trouver le maximum d’un tableau ?
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Recherches et tris » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
