Informatique · Classes prépa (CPGE) — 1ère année — ECS

Algorithmes de tri et de recherche

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Les algorithmes de tri permettent d'ordonner une liste $L$ de $n$ éléments.

Tri par sélection : On cherche le minimum dans $L[i:]$ et on l'échange avec $L[i]$ . Complexité : $O(n^2)$ .
Tri par insertion : On insère chaque élément $L[i]$ à sa place dans la partie déjà triée $L[0:i]$ . Complexité : $O(n^2)$ .
Tri à bulles : On échange les éléments adjacents s'ils sont mal ordonnés. Complexité : $O(n^2)$ .
Recherche séquentielle : Parcours complet de la liste. Complexité : $O(n)$ .
Recherche dichotomique : Nécessite une liste triée. On divise l'intervalle de recherche par 2 à chaque étape. Complexité : $O(\log n)$ .

Méthodes à maîtriser

Analyse de complexité : Compter le nombre d'opérations élémentaires en fonction de $n$ .
Trace d'exécution : Savoir remplir un tableau d'état des variables à chaque itération.
Choix de l'algorithme : Utiliser la dichotomie uniquement si la liste est triée.

Exemples corrigés

Exemple de recherche dichotomique : Pour chercher 7 dans [1, 3, 5, 7, 9].

$g=0, d=4, m=2$ . $L[2]=5 < 7$ . On cherche à droite.
$g=3, d=4, m=3$ . $L[3]=7$ . Trouvé !

Erreurs fréquentes

Oublier que la recherche dichotomique ne fonctionne que sur une liste triée.
Confondre l'indice $i$ et la valeur $L[i]$ .
Négliger le cas où l'élément recherché n'existe pas dans la liste.

L'essentiel du cours

Les algorithmes de tri permettent d'ordonner une liste $L$ de $n$ éléments.

Tri par sélection : On cherche le minimum dans $L[i:]$ et on l'échange avec $L[i]$. Complexité : $O(n^2)$.
Tri par insertion : On insère chaque élément $L[i]$ à sa place dans la partie déjà triée $L[0:i]$. Complexité : $O(n^2)$.
Tri à bulles : On échange les éléments adjacents s'ils sont mal ordonnés. Complexité : $O(n^2)$.
Recherche séquentielle : Parcours complet de la liste. Complexité : $O(n)$.
Recherche dichotomique : Nécessite une liste triée. On divise l'intervalle de recherche par 2 à chaque étape. Complexité : $O(\log n)$.

Méthodes à maîtriser

Analyse de complexité : Compter le nombre d'opérations élémentaires en fonction de $n$.
Trace d'exécution : Savoir remplir un tableau d'état des variables à chaque itération.
Choix de l'algorithme : Utiliser la dichotomie uniquement si la liste est triée.

Exemples corrigés

Exemple de recherche dichotomique : Pour chercher 7 dans [1, 3, 5, 7, 9].

$g=0, d=4, m=2$. $L[2]=5 < 7$. On cherche à droite.
$g=3, d=4, m=3$. $L[3]=7$. Trouvé !

Erreurs fréquentes

Oublier que la recherche dichotomique ne fonctionne que sur une liste triée.
Confondre l'indice $i$ et la valeur $L[i]$.
Négliger le cas où l'élément recherché n'existe pas dans la liste.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Algorithmes de tri et de recherche

1/4

Quelle est la complexité du tri par sélection ?

❓ Questions fréquentes

Kifach n3ref wach nst3mel tri par insertion wla sélection ?

Le tri par insertion est plus rapide si la liste est "presque triée".
Le tri par sélection fait toujours le même nombre de comparaisons, peu importe l'état initial.
En pratique, pour de petites listes, la différence est négligeable.

💡 À retenir : Choisis l'insertion pour des données partiellement ordonnées.

Chno hiya l'complexité dyal recherche dichotomique ?

La complexité est $O(\log n)$ car à chaque étape, on divise la taille de la zone de recherche par 2.

💡 À retenir : La dichotomie est exponentiellement plus rapide que la recherche séquentielle pour les grandes listes.

La complexité est $O(\log n)$ car à chaque étape, on divise la taille de la zone de recherche par 2.

💡 À retenir : La dichotomie est exponentiellement plus rapide que la recherche séquentielle pour les grandes listes.

Kifach n7seb l'complexité d'un algorithme ?

Identifie les boucles imbriquées.
Une boucle simple de $n$ itérations donne $O(n)$ .
Deux boucles imbriquées donnent $O(n^2)$ .

💡 À retenir : Le terme dominant détermine la complexité (on ignore les constantes).

Identifie les boucles imbriquées.
Une boucle simple de $n$ itérations donne $O(n)$.
Deux boucles imbriquées donnent $O(n^2)$.

💡 À retenir : Le terme dominant détermine la complexité (on ignore les constantes).

Qu'est-ce qu'un pivot dans le tri rapide ?

Le pivot est un élément choisi pour diviser la liste en deux sous-listes : les éléments inférieurs au pivot et ceux supérieurs.

💡 À retenir : Le choix du pivot influence grandement la performance de l'algorithme.

La recherche séquentielle est-elle toujours mauvaise ?

Non, elle est optimale pour une liste non triée de petite taille ou si l'on ne doit chercher qu'une seule fois.

💡 À retenir : Ne trie pas une liste juste pour faire une recherche unique.

Pourquoi le tri à bulles est-il peu utilisé ?

Parce qu'il effectue beaucoup d'échanges inutiles, ce qui le rend lent comparé aux algorithmes comme le tri fusion ou rapide.

💡 À retenir : Il est surtout pédagogique pour comprendre les échanges.

Est-ce que la recherche dichotomique peut marcher sur une liste de tuples ?

Oui, à condition que les tuples soient comparables selon le critère de tri utilisé.

💡 À retenir : La condition sine qua non est que la liste soit triée selon le critère de recherche.

Comment savoir si une liste est triée ?

Il faut parcourir la liste et vérifier que chaque élément est inférieur ou égal au suivant : L[i] <= L[i+1].

💡 À retenir : Un seul élément mal placé suffit à invalider le tri.

Est-ce que la complexité O(n^2) est toujours lente ?

Pour $n < 1000$ , c'est acceptable. Pour $n > 10^6$ , c'est trop lent (plusieurs minutes).

💡 À retenir : La complexité est cruciale pour les grands volumes de données.

Pour $n < 1000$, c'est acceptable. Pour $n > 10^6$, c'est trop lent (plusieurs minutes).

💡 À retenir : La complexité est cruciale pour les grands volumes de données.

Quelle est la différence entre tri stable et instable ?

Un tri stable préserve l'ordre relatif des éléments ayant la même valeur.

💡 À retenir : C'est important si on trie des objets selon plusieurs critères.

Peut-on faire une recherche dichotomique sur une liste chaînée ?

C'est déconseillé car l'accès à un indice $i$ dans une liste chaînée est en $O(n)$ , ce qui annule le gain de la dichotomie.

💡 À retenir : La dichotomie nécessite un accès direct (indexation).

C'est déconseillé car l'accès à un indice $i$ dans une liste chaînée est en $O(n)$, ce qui annule le gain de la dichotomie.

💡 À retenir : La dichotomie nécessite un accès direct (indexation).

Est-ce que le tri par sélection est efficace pour les grandes listes ?

Non, car sa complexité reste $O(n^2)$ même dans le meilleur des cas.

💡 À retenir : Préfère les algorithmes en $O(n \log n)$ pour les grandes données.

Non, car sa complexité reste $O(n^2)$ même dans le meilleur des cas.

💡 À retenir : Préfère les algorithmes en $O(n \log n)$ pour les grandes données.

✍️ Exercices type examen national

Exercice 1

Soit une liste $L = [12, 5, 8, 1, 9]$ . Appliquez manuellement l'algorithme de tri par insertion et donnez l'état de la liste après chaque itération.

Exercice 1

Soit une liste $L = [12, 5, 8, 1, 9]$. Appliquez manuellement l'algorithme de tri par insertion et donnez l'état de la liste après chaque itération.

Voir la correction détaillée : inscription gratuite

Exercice 2

Écrire une fonction Python recherche_dicho(L, cible) qui retourne l'indice de cible dans L ou -1 si absent.

Voir la correction détaillée : inscription gratuite

Exercice 3

On dispose d'une liste triée de 1024 éléments. Combien de comparaisons au maximum effectue la recherche dichotomique ?

Voir la correction détaillée : inscription gratuite

Un prof de Informatique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Informatique

Introduction à l'informatique et architecture des ordinateurs Algorithmique et programmation en Python : Les bases Structures de contrôle : Séquences, conditions et boucles Fonctions et portée des variables Types de données composés : Listes, tuples et chaînes de caractères Dictionnaires et ensembles Manipulation de fichiers Complexité algorithmique Récursivité Introduction au calcul scientifique avec NumPy Visualisation de données avec Matplotlib Bases de données relationnelles et langage SQL