On veut chercher UNE seule valeur dans un tableau non trié de 1 000 éléments. Quelle stratégie est la plus efficace ?

Faire directement une recherche séquentielle

Trier d'abord par insertion, puis faire une dichotomie

Trier d'abord par sélection, puis faire une recherche séquentielle

Faire une dichotomie directement, sans trier

Dans la recherche dichotomique, un élève remplace g = m + 1 par g = m. Que se passe-t-il si on cherche la valeur 8 dans [2, 5] ?

L'algorithme boucle indéfiniment

L'algorithme renvoie None comme prévu

L'algorithme renvoie l'indice 1

Python lève une erreur IndexError

Quelle condition doit obligatoirement être remplie pour utiliser une recherche dichotomique ?

Le tableau ne doit contenir que des entiers

Le tableau doit avoir une taille paire

Le tableau doit contenir la valeur cherchée

Quel est le principe du tri par sélection ?

Chercher le plus petit élément de la partie non triée et l'échanger avec la première case non triée

Comparer les éléments deux à deux et les échanger s'ils sont mal ordonnés

Couper le tableau en deux et trier chaque moitié

Insérer chaque élément à sa place dans la partie déjà triée

Le tri par insertion est comparé à quelle situation de la vie courante ?

Ranger une main de cartes en glissant chaque nouvelle carte à sa place parmi celles déjà tenues

Ranger des livres en cherchant à chaque fois le plus petit du tas

Séparer un paquet de cartes en deux tas puis les fusionner

Jeter les cartes en trop jusqu'à ce que le paquet soit trié

Algorithmes de tri et de recherche

Première · NSI · Traitement de données et algorithmique

Traitement de données et algorithmique

Rechercher dans un tableau : séquentielle et dichotomie

La recherche séquentielle (ou linéaire)

Chercher une valeur dans un tableau est l'opération la plus banale de l'informatique — et pourtant il existe deux façons très différentes de le faire. L'une marche toujours mais peut être lente ; l'autre est spectaculairement rapide, à condition que le tableau soit trié.

Commençons par la première. Le principe est direct : on parcourt le tableau case par case, du début à la fin, et on compare chaque élément à la valeur cherchée. Dès qu'on la trouve, on renvoie son indice. Si on arrive au bout sans rien trouver, c'est que la valeur est absente.

def recherche(tab, v):
    for i in range(len(tab)):
        if tab[i] == v:
            return i
    return None

Cet algorithme ne fait aucune hypothèse sur le tableau : trié ou non, il fonctionne. C'est sa grande force.

La recherche dichotomique

Si le tableau est trié dans l'ordre croissant, on peut faire beaucoup mieux. On compare la valeur cherchée à l'élément du milieu : s'il est trop grand, la valeur ne peut être que dans la moitié gauche ; s'il est trop petit, elle ne peut être que dans la moitié droite. Dans les deux cas, on élimine la moitié du tableau d'un coup. On recommence sur la moitié restante, et ainsi de suite.

def dicho(tab, v):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == v:
            return m
        elif tab[m] < v:
            g = m + 1
        else:
            d = m - 1
    return None

	Recherche séquentielle	Recherche dichotomique
Tableau trié nécessaire ?	Non	Oui, obligatoirement
Principe	Parcourir case par case	Couper l'intervalle en deux à chaque tour
Coût dans le pire des cas	n comparaisons (linéaire)	environ log2(n) comparaisons (logarithmique)
Pour n = 1 000	jusqu'à 1 000 comparaisons	au plus 10 comparaisons
Pour n = 1 000 000	jusqu'à 1 000 000 comparaisons	au plus 20 comparaisons

Traitement de données et algorithmique

Les tris par sélection et par insertion

Trier un tableau, c'est ranger ses éléments dans l'ordre croissant. Au programme de première, deux algorithmes de tri : le tri par sélection et le tri par insertion. Tous deux sont simples à écrire, tous deux ont un coût quadratique — mais ils ne travaillent pas du tout de la même manière.

Le tri par insertion

C'est le tri du joueur de cartes : on prend les éléments un par un et on insère chacun à sa place dans la partie déjà triée, en décalant vers la droite tous ceux qui sont plus grands que lui.

def tri_insertion(tab):
    for i in range(1, len(tab)):
        val = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > val:
            tab[j + 1] = tab[j]
            j = j - 1
        tab[j + 1] = val

La grosse différence avec la sélection : la partie gauche est bien triée à chaque étape, mais ses éléments ne sont pas forcément à leur place définitive — une valeur plus petite peut encore arriver et tout décaler.

Prouver qu'un tri est correct : invariant et terminaison

Terminaison — Exhibe un « variant » : une quantité entière, positive, qui décroît strictement à chaque tour. Pour la boucle for, c'est immédiat (le nombre de tours est fixé) ; pour le while du tri par insertion, c'est j + 1, qui décroît de 1 à chaque passage et reste positif ou nul.
Invariant — Trouve une propriété vraie avant la boucle, préservée par chaque tour, et qui donne le résultat à la sortie.
Tri par sélection — Invariant : « après l'étape i, les cases 0 à i contiennent les i + 1 plus petits éléments du tableau, rangés dans l'ordre croissant ». À la fin (i = n − 2), tout le tableau est trié.
Tri par insertion — Invariant : « avant l'étape i, les cases 0 à i − 1 forment un tableau trié ». À la fin (i = n − 1 traité), les n cases sont triées.
Rappelle-toi que les deux tris sont « en place » : ils modifient le tableau donné, sans en créer un nouveau. Ils ne renvoient donc rien (None).

Critère	Tri par sélection	Tri par insertion
Idée	Chercher le minimum et l'échanger	Insérer l'élément courant à sa place
Comparaisons dans le pire des cas	n(n−1)/2, toujours	n(n−1)/2 (tableau trié à l'envers)
Comparaisons dans le meilleur des cas	n(n−1)/2, toujours	n − 1 (tableau déjà trié)
Coût	Quadratique dans tous les cas	Quadratique au pire, linéaire au mieux
Échanges / décalages	au plus n − 1 échanges	beaucoup de décalages possibles
Invariant	Les i+1 premières cases sont les plus petits éléments, à leur place définitive	Les i premières cases sont triées entre elles

Les erreurs classiques

Dire que le tri par sélection est plus rapide sur un tableau déjà trié : faux. Il cherche quand même le minimum de chaque sous-tableau, donc il fait toujours n(n−1)/2 comparaisons.
Oublier la condition j >= 0 dans le while du tri par insertion : quand la valeur est plus petite que tout, j descend à −1 et tab[−1] désigne la dernière case en Python. Le tableau est alors corrompu, sans message d'erreur.
Faire l'échange en deux lignes sans variable temporaire (tab[i] = tab[imin] puis tab[imin] = tab[i]) : la première valeur est écrasée. En Python, l'affectation simultanée tab[i], tab[imin] = tab[imin], tab[i] règle le problème.
Confondre coût quadratique et coût linéaire : pour n = 100, un tri quadratique fait environ 5 000 comparaisons, contre 100 pour un parcours simple.

Exercices corrigés

On applique un tri par sélection au tableau [7, 3, 9, 1, 5]. Quel est le tableau après la PREMIÈRE étape (i = 0) ?
- A.[3, 7, 9, 1, 5]
- B.[1, 3, 5, 7, 9]
- C.[1, 3, 9, 7, 5]Bonne réponse
- D.[1, 7, 9, 3, 5]
Réponse : C — [1, 3, 9, 7, 5]
À l'étape i = 0, on cherche le minimum de tout le tableau : c'est 1, en position 3. On l'échange avec la case 0, qui contient 7. Le 1 va en case 0 et le 7 va en case 3 : on obtient [1, 3, 9, 7, 5]. Attention, seules DEUX cases bougent, les autres ne sont pas touchées — la réponse [1, 7, 9, 3, 5] correspond à un échange mal recopié. [3, 7, 9, 1, 5] serait le résultat d'un premier tour de tri par INSERTION, et [1, 3, 5, 7, 9] est le tableau complètement trié, ce qui demande encore deux étapes.
Dans le tableau trié [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 à 9), on cherche 23 par dichotomie. Quel est le DEUXIÈME indice testé ?
- A.4
- B.5
- C.7Bonne réponse
- D.6
Réponse : C — 7
Premier tour : g = 0, d = 9, donc m = (0+9)//2 = 4 et tab[4] = 16. Comme 16 < 23, la valeur est à droite : g devient 5. Deuxième tour : m = (5+9)//2 = 14//2 = 7, on teste donc tab[7] = 56. C'est le deuxième indice testé. (Comme 56 > 23, d passera à 6, puis le troisième test portera sur l'indice 5, où 23 sera trouvé.) L'indice 4 est le premier testé, pas le deuxième.
On applique un tri par insertion à [7, 3, 9, 1, 5]. Quel est le tableau après le tour i = 3 (insertion de la valeur 1) ?
- A.[1, 3, 7, 9, 5]Bonne réponse
- B.[1, 3, 5, 7, 9]
- C.[3, 7, 1, 9, 5]
- D.[1, 7, 9, 3, 5]
Réponse : A — [1, 3, 7, 9, 5]
Après i = 1 le tableau vaut [3, 7, 9, 1, 5], après i = 2 il ne change pas car 9 est déjà plus grand que 7 : [3, 7, 9, 1, 5]. Au tour i = 3, on retire la valeur 1 et on décale 9, puis 7, puis 3 d'une case vers la droite ; 1 se pose en case 0. On obtient [1, 3, 7, 9, 5]. Le 5 n'est pas encore traité : c'est l'objet du tour suivant, qui donnera l'option 2.
On veut chercher UNE seule valeur dans un tableau non trié de 1 000 éléments. Quelle stratégie est la plus efficace ?
- A.Trier d'abord par insertion, puis faire une dichotomie
- B.Faire directement une recherche séquentielleBonne réponse
- C.Trier d'abord par sélection, puis faire une recherche séquentielle
- D.Faire une dichotomie directement, sans trier
Réponse : B — Faire directement une recherche séquentielle
La recherche séquentielle coûte au pire 1 000 comparaisons. Trier d'abord coûterait de l'ordre de 1000 × 999 / 2 ≈ 500 000 comparaisons, soit 500 fois plus cher, avant même de commencer à chercher ! Trier ne devient rentable que si l'on prévoit BEAUCOUP de recherches sur le même tableau. Quant à la dichotomie sur un tableau non trié, elle donne un résultat faux : ce n'est pas une option.
Dans la recherche dichotomique, un élève remplace g = m + 1 par g = m. Que se passe-t-il si on cherche la valeur 8 dans [2, 5] ?
- A.L'algorithme renvoie None comme prévu
- B.L'algorithme renvoie l'indice 1
- C.L'algorithme boucle indéfinimentBonne réponse
- D.Python lève une erreur IndexError
Réponse : C — L'algorithme boucle indéfiniment
Déroulons : g = 0, d = 1, m = (0+1)//2 = 0, tab[0] = 2 < 8 donc g = m = 0 — la borne ne bouge pas. On recalcule m = 0, on retrouve 2 < 8, g reste 0... et ainsi de suite indéfiniment. Le variant d − g ne décroît plus : la preuve de terminaison s'effondre. C'est pour cela qu'on écrit g = m + 1 : on exclut le milieu déjà testé, ce qui garantit une décroissance stricte de l'intervalle. Une boucle infinie ne lève aucune erreur, elle fige simplement le programme.
Quelle condition doit obligatoirement être remplie pour utiliser une recherche dichotomique ?
- A.Le tableau ne doit contenir que des entiers
- B.Le tableau doit être triéBonne réponse
- C.Le tableau doit avoir une taille paire
- D.Le tableau doit contenir la valeur cherchée
Réponse : B — Le tableau doit être trié
La dichotomie repose entièrement sur le fait que comparer la valeur cherchée à l'élément du milieu permet d'éliminer une moitié entière. Cela n'a de sens que si le tableau est trié. Le type des éléments importe peu (il suffit de pouvoir les comparer), la taille peut être paire ou impaire, et l'algorithme sait très bien répondre « absent » quand la valeur n'y est pas.
Combien de comparaisons fait au maximum une recherche séquentielle dans un tableau de 50 éléments ?
- A.6
- B.25
- C.50Bonne réponse
- D.2500
Réponse : C — 50
Dans le pire des cas — valeur en dernière position ou absente — la recherche séquentielle parcourt toutes les cases, soit 50 comparaisons. Le coût est donc linéaire en n. Répondre 6 serait le coût d'une dichotomie (log2(50) ≈ 5,6), 25 serait la moitié (c'est le coût MOYEN, pas le pire cas) et 2500 = 50² n'a rien à voir : ce serait le coût d'un tri quadratique.
Quel est le principe du tri par sélection ?
- A.Comparer les éléments deux à deux et les échanger s'ils sont mal ordonnés
- B.Couper le tableau en deux et trier chaque moitié
- C.Insérer chaque élément à sa place dans la partie déjà triée
- D.Chercher le plus petit élément de la partie non triée et l'échanger avec la première case non triéeBonne réponse
Réponse : D — Chercher le plus petit élément de la partie non triée et l'échanger avec la première case non triée
Le tri par sélection sélectionne (d'où son nom) le minimum de la partie non triée et le place directement à sa position définitive par un échange. « Insérer chaque élément à sa place » décrit le tri par insertion ; « comparer deux à deux et échanger » décrit le tri à bulles, hors programme ; « couper en deux et trier chaque moitié » décrit le tri fusion, qui relève de la terminale.
Que renvoie la fonction recherche(tab, v) écrite dans le cours lorsque la valeur v n'est pas dans le tableau ?
- A.NoneBonne réponse
- B.−1
- C.0
- D.Une erreur IndexError
Réponse : A — None
La boucle for parcourt tout le tableau sans jamais rencontrer v, donc aucun return i n'est exécuté. On sort de la boucle et on atteint le return None final. Renvoyer −1 est une convention possible dans d'autres langages, mais ce n'est pas ce que fait ce code. Renvoyer 0 serait faux et dangereux : 0 est un indice valide ! Et il n'y a pas d'erreur : range(len(tab)) ne dépasse jamais les bornes.
Le tri par insertion est comparé à quelle situation de la vie courante ?
- A.Ranger des livres en cherchant à chaque fois le plus petit du tas
- B.Ranger une main de cartes en glissant chaque nouvelle carte à sa place parmi celles déjà tenuesBonne réponse
- C.Séparer un paquet de cartes en deux tas puis les fusionner
- D.Jeter les cartes en trop jusqu'à ce que le paquet soit trié
Réponse : B — Ranger une main de cartes en glissant chaque nouvelle carte à sa place parmi celles déjà tenues
Le tri par insertion, c'est exactement le geste du joueur de cartes : la main gauche contient les cartes déjà triées, et chaque nouvelle carte est insérée à sa place en décalant les plus grandes. L'option 1 décrit le tri par sélection, l'option 3 le tri fusion. Un tri ne supprime jamais d'éléments : il les réordonne.
Combien d'étapes au maximum une recherche dichotomique effectue-t-elle dans un tableau trié de 15 éléments ?
- A.4Bonne réponse
- B.8
- C.15
- D.2
Réponse : A — 4
À chaque étape, la zone de recherche est divisée par deux : 15 → 7 → 3 → 1 → 0. Il faut donc 4 étapes au maximum, ce qui correspond bien à log2(16) = 4. Répondre 8 serait diviser une seule fois par deux, et 15 serait le coût de la recherche séquentielle. Retiens l'ordre de grandeur : 15 éléments, 4 étapes ; 1023 éléments, 10 étapes.
Combien de comparaisons effectue un tri par sélection sur un tableau de 6 éléments ?
- A.6
- B.36
- C.5
- D.15Bonne réponse
Réponse : D — 15
À l'étape i = 0 on compare 5 éléments au minimum courant, puis 4, puis 3, puis 2, puis 1 : total 5 + 4 + 3 + 2 + 1 = 15. C'est bien la formule n(n−1)/2 = 6 × 5 / 2 = 15. Répondre 5 (= n − 1) correspond au nombre d'ÉCHANGES, pas de comparaisons, et 36 = 6² surestime : la boucle interne raccourcit à chaque tour.

S'entraîner sur ce chapitre

Ce chapitre compte 36 exercices corrigés dans l'application, avec le suivi de ta progression.

Commencer les exercices