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

Algorithmique avancée : Recherche et tri

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

La recherche et le tri sont fondamentaux pour manipuler des données.

Recherche séquentielle : Parcours complet du tableau. Complexité $O(n)$ .
Recherche dichotomique : Nécessite un tableau trié. On divise l'intervalle de recherche par deux à chaque étape. Complexité $O(\log n)$ .
Tri à bulles : Échange les éléments adjacents s'ils sont mal ordonnés.
Tri par sélection : Cherche le minimum et l'échange avec la première position non triée.
Tri par insertion : Insère chaque élément à sa place dans la partie déjà triée.

Méthodes à maîtriser

Recherche dichotomique : Toujours vérifier si le tableau est trié avant. Calculer le milieu m = (g + d) // 2.
Tri par sélection : Utiliser deux boucles imbriquées. La boucle externe parcourt le tableau, l'interne cherche le min.
Échange de valeurs : Utiliser a, b = b, a en Python pour éviter une variable temporaire.

Exemples corrigés

Exemple de recherche dichotomique :

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

Erreurs fréquentes

Oublier que l'indice commence à 0.
Confondre g <= d avec g < d dans la boucle dichotomique.
Utiliser la recherche dichotomique sur un tableau non trié.

L'essentiel du cours

La recherche et le tri sont fondamentaux pour manipuler des données.

Recherche séquentielle : Parcours complet du tableau. Complexité $O(n)$.
Recherche dichotomique : Nécessite un tableau trié. On divise l'intervalle de recherche par deux à chaque étape. Complexité $O(\log n)$.
Tri à bulles : Échange les éléments adjacents s'ils sont mal ordonnés.
Tri par sélection : Cherche le minimum et l'échange avec la première position non triée.
Tri par insertion : Insère chaque élément à sa place dans la partie déjà triée.

Méthodes à maîtriser

Recherche dichotomique : Toujours vérifier si le tableau est trié avant. Calculer le milieu m = (g + d) // 2.
Tri par sélection : Utiliser deux boucles imbriquées. La boucle externe parcourt le tableau, l'interne cherche le min.
Échange de valeurs : Utiliser a, b = b, a en Python pour éviter une variable temporaire.

Exemples corrigés

Exemple de recherche dichotomique :

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

Erreurs fréquentes

Oublier que l'indice commence à 0.
Confondre g <= d avec g < d dans la boucle dichotomique.
Utiliser la recherche dichotomique sur un tableau non trié.

🌉 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

🎯 Algorithmique avancée : Recherche et tri

1/4

Quelle est la complexité du tri à bulles dans le pire des cas ?

❓ Questions fréquentes

Est-ce que la recherche dichotomique est toujours plus rapide ?

Non, elle n'est plus rapide que si le tableau est déjà trié. Si le tableau n'est pas trié, il faut d'abord le trier, ce qui prend du temps. Pour un petit tableau, la recherche séquentielle est souvent suffisante.

💡 À retenir : La dichotomie est efficace pour les grands volumes de données triées.

Kifach n7seb l'indice dyal lwest f dichotomie ila kan l'intervalle kbir?

Katakhod l'indice dyal lbidaya g (gauche).
Katakhod l'indice dyal nihaya d (droite).
L'indice dyal lwest m houwa (g + d) // 2.

💡 À retenir : Utilisez toujours la division entière // pour obtenir un indice entier.

Pourquoi le tri à bulles est-il considéré comme lent ?

Parce qu'il effectue un grand nombre de comparaisons et d'échanges, surtout si le tableau est inversé. Sa complexité est $O(n^2)$ .

💡 À retenir : À éviter pour les très grands tableaux.

Parce qu'il effectue un grand nombre de comparaisons et d'échanges, surtout si le tableau est inversé. Sa complexité est $O(n^2)$.

💡 À retenir : À éviter pour les très grands tableaux.

Chno hiya l'utilité dyal tri par insertion?

Kankhedmou bih bzaf ila kan l'utilisateur kayzid 3anasir wa7ed b wa7ed l tableau li mratb, bach may3awdch yretbou kaml.

💡 À retenir : Très efficace pour les tableaux presque triés.

Est-ce que le tri par sélection change l'ordre des éléments égaux ?

Oui, le tri par sélection n'est pas "stable". Il peut modifier l'ordre relatif des éléments ayant la même valeur.

💡 À retenir : La stabilité est importante si on trie des objets complexes.

Kifach n3ref wach l'algo diali khdem mezian?

Testih b tableau khawi.
Testih b tableau fih 3onsor wa7ed.
Testih b tableau mratb o tableau m3kous.

💡 À retenir : Un bon algo doit gérer les cas limites.

Quelle est la différence entre trier et rechercher ?

Trier consiste à organiser les éléments selon un ordre (croissant/décroissant). Rechercher consiste à trouver la position d'un élément spécifique dans une structure.

💡 À retenir : Le tri facilite souvent la recherche.

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

Oui, car $O(n)$ signifie que le temps augmente linéairement avec la taille des données, alors que $O(n^2)$ augmente beaucoup plus vite.

💡 À retenir : Plus la complexité est basse, plus l'algorithme est performant.

Oui, car $O(n)$ signifie que le temps augmente linéairement avec la taille des données, alors que $O(n^2)$ augmente beaucoup plus vite.

💡 À retenir : Plus la complexité est basse, plus l'algorithme est performant.

Chhal dyal l'espace kayakhod l'algo?

L'espace dépend des variables auxiliaires utilisées. Si on crée un nouveau tableau, l'espace est $O(n)$ . Si on trie sur place, c'est $O(1)$ .

💡 À retenir : Le tri "sur place" économise la mémoire.

L'espace dépend des variables auxiliaires utilisées. Si on crée un nouveau tableau, l'espace est $O(n)$. Si on trie sur place, c'est $O(1)$.

💡 À retenir : Le tri "sur place" économise la mémoire.

Pourquoi on utilise // au lieu de / en Python ?

En Python, / donne un nombre flottant (ex: 2.5), or les indices d'un tableau doivent être des entiers. // permet d'obtenir la partie entière.

💡 À retenir : Les indices sont toujours des entiers.

Est-ce que le tri par insertion est toujours le meilleur ?

Non, il est excellent pour les petits tableaux ou les tableaux presque triés, mais pour des millions de données, d'autres algorithmes (comme le tri rapide) sont préférables.

💡 À retenir : Chaque algorithme a son domaine d'application.

Comment savoir si un tableau est trié ?

Il faut parcourir le tableau et vérifier si chaque élément est inférieur ou égal à son suivant. Si on trouve un élément plus grand que le suivant, le tableau n'est pas trié.

💡 À retenir : Un seul contre-exemple suffit pour invalider le tri.

✍️ Exercices type examen national

Exercice 1

Soit une liste L = [2, 4, 6, 8, 10]. On cherche la valeur 7 par dichotomie. Montrer les étapes de recherche.

Voir la correction détaillée : inscription gratuite

Exercice 2

On considère une liste L = [12, 5, 8, 1, 9]. Appliquer manuellement l'algorithme de tri par sélection pour trier cette liste par ordre croissant. Détailler chaque étape.

Voir la correction détaillée : inscription gratuite

Exercice 3

Écrire une fonction Python recherche_min(tab) qui retourne l'indice du plus petit élément d'une liste non vide tab.

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

Architecture des ordinateurs et systèmes d'exploitation Algorithmique et programmation en Python : Les bases Structures de contrôle : Séquences, conditions et boucles Les fonctions et la modularité Les structures de données : Listes, tuples et dictionnaires Traitement de fichiers Bases de données et langage SQL Introduction à la complexité algorithmique