Informatique · Classes prépa (CPGE) — 2ème année — TSI

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 d'éléments. La complexité est mesurée en fonction de la taille $n$ de la liste :

Tri par sélection : $O(n^2)$ . Recherche du minimum et échange.
Tri par insertion : $O(n^2)$ (pire cas), $O(n)$ (meilleur cas). Efficace pour les petites listes.
Tri fusion : $O(n \log n)$ . Diviser pour régner, stable mais nécessite de la mémoire supplémentaire.
Tri rapide (QuickSort) : $O(n \log n)$ en moyenne, $O(n^2)$ au pire cas. Très rapide en pratique.
Recherche séquentielle : $O(n)$ . Parcours linéaire.
Recherche dichotomique : $O(\log n)$ . Nécessite une liste triée.

Méthodes à maîtriser

Analyse de complexité : Compter le nombre d'opérations élémentaires (comparaisons/affectations).
Exécution manuelle : Être capable de dérouler un tri (ex: état de la liste après chaque itération).
Choix de l'algorithme : Savoir quand utiliser la dichotomie (liste triée) vs séquentielle.

Exemples corrigés

Exemple Tri par insertion : Pour [5, 2, 9], on prend 2, on le compare à 5, on décale 5, on insère 2 : [2, 5, 9]. Exemple Dichotomie : Chercher 7 dans [1, 3, 5, 7, 9]. Milieu = 5. $7 > 5$ , on cherche dans [7, 9]. Milieu = 7. Trouvé.

Erreurs fréquentes

Oublier que la dichotomie ne fonctionne que sur des listes déjà triées.
Confondre la complexité au pire cas et au meilleur cas.
Ne pas gérer correctement les indices (débordement IndexError) lors des boucles.

L'essentiel du cours

Les algorithmes de tri permettent d'ordonner une liste d'éléments. La complexité est mesurée en fonction de la taille $n$ de la liste :

Tri par sélection : $O(n^2)$. Recherche du minimum et échange.
Tri par insertion : $O(n^2)$ (pire cas), $O(n)$ (meilleur cas). Efficace pour les petites listes.
Tri fusion : $O(n \log n)$. Diviser pour régner, stable mais nécessite de la mémoire supplémentaire.
Tri rapide (QuickSort) : $O(n \log n)$ en moyenne, $O(n^2)$ au pire cas. Très rapide en pratique.
Recherche séquentielle : $O(n)$. Parcours linéaire.
Recherche dichotomique : $O(\log n)$. Nécessite une liste triée.

Méthodes à maîtriser

Analyse de complexité : Compter le nombre d'opérations élémentaires (comparaisons/affectations).
Exécution manuelle : Être capable de dérouler un tri (ex: état de la liste après chaque itération).
Choix de l'algorithme : Savoir quand utiliser la dichotomie (liste triée) vs séquentielle.

Exemples corrigés

Erreurs fréquentes

Oublier que la dichotomie ne fonctionne que sur des listes déjà triées.
Confondre la complexité au pire cas et au meilleur cas.
Ne pas gérer correctement les indices (débordement IndexError) lors des boucles.

🌉 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é de la recherche dichotomique ?

❓ Questions fréquentes

Est-ce que le tri rapide est toujours plus rapide que le tri fusion ?

Non. Bien que le tri rapide soit souvent plus rapide en pratique, son pire cas est en $O(n^2)$ si le pivot est mal choisi (ex: liste déjà triée). Le tri fusion garantit toujours $O(n \log n)$ .

💡 À retenir : Le tri fusion est stable et prévisible, le tri rapide est plus rapide en moyenne mais instable.

Non. Bien que le tri rapide soit souvent plus rapide en pratique, son pire cas est en $O(n^2)$ si le pivot est mal choisi (ex: liste déjà triée). Le tri fusion garantit toujours $O(n \log n)$.

💡 À retenir : Le tri fusion est stable et prévisible, le tri rapide est plus rapide en moyenne mais instable.

Kifach n7seb l'complexité d'un algorithme récursif ?

On utilise une relation de récurrence. Par exemple, pour le tri fusion : $T(n) = 2T(n/2) + O(n)$ . Selon le théorème maître, cela donne $O(n \log n)$ .

💡 À retenir : Diviser par deux à chaque étape donne souvent du $\log n$ .

On utilise une relation de récurrence. Par exemple, pour le tri fusion : $T(n) = 2T(n/2) + O(n)$. Selon le théorème maître, cela donne $O(n \log n)$.

💡 À retenir : Diviser par deux à chaque étape donne souvent du $\log n$.

Est-ce qu'on peut faire une recherche dichotomique sur une liste non triée ?

Non, absolument pas. La dichotomie repose sur le fait que si l'élément cherché est plus grand que le milieu, il est forcément dans la moitié droite. Si la liste n'est pas triée, cette logique tombe.

💡 À retenir : Liste triée = Dichotomie possible. Liste non triée = Recherche séquentielle obligatoire.

Chno hiya l'farq bin tri stable o instable ?

Un tri est stable si deux éléments égaux gardent leur ordre relatif initial. C'est important quand on trie des objets selon plusieurs critères.

💡 À retenir : Tri fusion est stable, Tri rapide ne l'est pas.

Pourquoi le tri par insertion est-il utilisé pour les petites listes ?

Parce qu'il a une très faible constante de complexité et qu'il est très simple à implémenter. Pour $n < 20$ , il est souvent plus rapide que le tri fusion.

💡 À retenir : Complexité théorique n'est pas toujours égale à performance réelle.

Parce qu'il a une très faible constante de complexité et qu'il est très simple à implémenter. Pour $n < 20$, il est souvent plus rapide que le tri fusion.

💡 À retenir : Complexité théorique n'est pas toujours égale à performance réelle.

Wach l'algorithme d'tri par sélection kayghyyer l'liste l'asliya ?

Oui, le tri par sélection est un algorithme "in-place", il modifie la liste en échangeant les éléments directement dans la mémoire allouée.

💡 À retenir : In-place = pas besoin de liste supplémentaire.

Comment choisir le pivot dans le QuickSort ?

On peut prendre le premier élément, le dernier, ou mieux, le médian de trois éléments pour éviter le pire cas $O(n^2)$ .

💡 À retenir : Un bon pivot est proche de la médiane des valeurs.

On peut prendre le premier élément, le dernier, ou mieux, le médian de trois éléments pour éviter le pire cas $O(n^2)$.

💡 À retenir : Un bon pivot est proche de la médiane des valeurs.

Est-ce que la recherche séquentielle est toujours inutile ?

Non, elle est nécessaire si la liste n'est pas triée et qu'on ne veut pas perdre de temps à la trier avant de chercher.

💡 À retenir : Si on ne cherche qu'une seule fois, le coût du tri dépasse le gain de la dichotomie.

Kifach n3ref wach l'algorithme d'tri est efficace ?

On regarde sa complexité temporelle ( $O(n \log n)$ est idéal) et sa complexité spatiale (mémoire utilisée).

💡 À retenir : $O(n^2)$ est à éviter pour les grandes listes ( $n > 10^4$ ).

On regarde sa complexité temporelle ($O(n \log n)$ est idéal) et sa complexité spatiale (mémoire utilisée).

💡 À retenir : $O(n^2)$ est à éviter pour les grandes listes ($n > 10^4$).

Le tri à bulles est-il recommandé en entreprise ?

Non, il est principalement pédagogique. Sa complexité $O(n^2)$ le rend très lent pour les données réelles.

💡 À retenir : À utiliser uniquement pour apprendre le concept.

Non, il est principalement pédagogique. Sa complexité $O(n^2)$ le rend très lent pour les données réelles.

💡 À retenir : À utiliser uniquement pour apprendre le concept.

Quelle est la différence entre sort() et sorted() en Python ?

sort() modifie la liste sur place (in-place), sorted() renvoie une nouvelle liste triée sans modifier l'originale.

💡 À retenir : sort() = gain de mémoire, sorted() = préservation des données.

Est-ce que la complexité O(n log n) est la meilleure possible ?

Pour les tris basés sur des comparaisons, oui, c'est la borne inférieure théorique.

💡 À retenir : On ne peut pas faire mieux que $O(n \log n)$ avec des comparaisons.

Pour les tris basés sur des comparaisons, oui, c'est la borne inférieure théorique.

💡 À retenir : On ne peut pas faire mieux que $O(n \log n)$ avec des comparaisons.

✍️ Exercices type examen national

Exercice 1

Soit la liste L = [12, 5, 8, 1, 9]. Appliquer manuellement l'algorithme de tri par sélection et donner 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, val) qui retourne l'indice de val dans L ou -1 si absent.

Voir la correction détaillée : inscription gratuite

Exercice 3

Analyser la complexité du tri à bulles. Pourquoi est-il en $O(n^2)$ ?

Exercice 3

Analyser la complexité du tri à bulles. Pourquoi est-il en $O(n^2)$ ?

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

Révision et approfondissement du langage Python Complexité des algorithmes Structures de données : Listes, Piles et Files Structures de données : Arbres binaires et Arbres binaires de recherche Graphes : Représentation et parcours (BFS, DFS)Programmation dynamique Bases de données relationnelles et langage SQL Architecture des ordinateurs et systèmes d'exploitation