Najah.
Mon plan de révision⚡ Défi flash

Algorithmique · Écoles d'ingénieurs — ENSIAS

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 par le nombre d'opérations élémentaires (comparaisons/échanges).

  • Tri élémentaires ($O(n^2)$) : Sélection, Insertion, Bulles.
  • Tri efficaces ($O(n \log n)$) : Tri Fusion (Divide & Conquer), Tri Rapide (Partition).
  • Recherche : Séquentielle ($O(n)$) vs Dichotomique ($O(\log n)$ sur tableau trié).

Méthodes à maîtriser

  1. Analyse de complexité : Compter les boucles imbriquées pour déterminer $O(f(n))$.
  2. Exécution manuelle : Savoir tracer les étapes d'un tri (ex: état du tableau après chaque itération).
  3. Choix de l'algorithme : Utiliser la dichotomie uniquement si le tableau est trié.

Exemples corrigés

  • Tri par insertion : Pour insérer $T[i]$, on décale les éléments $T[j] > T[i]$ vers la droite.
  • Recherche dichotomique : $mil = (g + d) // 2$. Si $T[mil] < cible$, on cherche à droite ($g = mil + 1$).

Erreurs fréquentes

  • Confondre la complexité moyenne et la pire complexité du Tri Rapide ($O(n^2)$ dans le pire cas).
  • Oublier que la recherche dichotomique nécessite un tableau préalablement trié.
  • Inverser les indices lors de la fusion dans le Tri Fusion.

🌉 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.

Défi flash : 4 questions

Sans compte

🎯 Algorithmes de tri et de recherche

1/4

Quelle est la complexité de la recherche séquentielle ?

❓ Questions fréquentes

Quelle est la différence entre un tri stable et instable ?
  1. Un tri est stable si l'ordre relatif des éléments ayant des clés identiques est préservé.
  2. Exemple : si on trie des étudiants par note, un tri stable garde les étudiants ayant la même note dans leur ordre d'apparition initial.
  3. Le tri par insertion est stable, alors que le tri rapide (QuickSort) ne l'est généralement pas.

💡 À retenir : La stabilité est cruciale quand on trie des données selon plusieurs critères successifs.

Kifach n7seb l'complexité dyal chi algorithme fih boucles imbriquées ?
  1. Katchouf ch7al mn boucle 3ndk.
  2. Ila 3ndk boucle wa7da katmchi mn 1 l'n, l'complexité hiya $O(n)$.
  3. Ila 3ndk boucle dakhla f boucle (nested), katdir $n \times n = O(n^2)$.

💡 À retenir : Dima 7seb l'nombre de répétitions dyal l'instruction li katsma "opération élémentaire".

Est-ce que le tri fusion est toujours meilleur que le tri rapide ?
  1. Non, cela dépend du contexte.
  2. Le tri fusion garantit $O(n \log n)$ mais nécessite $O(n)$ d'espace mémoire supplémentaire.
  3. Le tri rapide est souvent plus rapide en pratique (meilleure localité mémoire) et ne nécessite qu'un espace $O(\log n)$.

💡 À retenir : Le tri fusion est préférable si la stabilité est requise ou si la mémoire n'est pas une contrainte.

Chno hiya l'7ala li kankhtaro fiha l'recherche dichotomique ?
  1. Kankhtaro l'recherche dichotomique ghir ila kan l'tableau trié (mratb).
  2. Ila kan l'tableau machi mratb, khassna ndiro recherche séquentielle $O(n)$.

💡 À retenir : Dichotomie = Tableau trié obligatoire.

Pourquoi le pire cas du tri rapide est O(n^2) ?
  1. Il survient quand le pivot choisi est systématiquement le plus petit ou le plus grand élément.
  2. Le tableau n'est pas divisé en deux, mais en 1 et $n-1$ éléments.
  3. La récursion se fait $n$ fois au lieu de $\log n$.

💡 À retenir : Le choix du pivot (ex: pivot aléatoire) est essentiel pour éviter ce cas.

Kifach n3ref wach l'algorithme dyali "in-place" ?
  1. "In-place" katz3ni l'algorithme makay7tajch tableau khor (mémoire supplémentaire) bach ykhdem.
  2. Tri par sélection = in-place.
  3. Tri fusion = pas in-place (kay7taj tableau temporaire).

💡 À retenir : In-place = $O(1)$ espace mémoire auxiliaire.

Quelle est la complexité de la recherche dans un arbre binaire de recherche ?
  1. En moyenne, c'est $O(\log n)$ car on élimine la moitié des nœuds à chaque comparaison.
  2. Dans le pire cas (arbre dégénéré en liste), c'est $O(n)$.

💡 À retenir : L'efficacité dépend de l'équilibre de l'arbre.

Est-ce que le tri à bulles est efficace pour les grands tableaux ?
  1. Non, sa complexité est $O(n^2)$.
  2. Pour $n=10^6$, il fera environ $10^{12}$ opérations, ce qui est trop lent.

💡 À retenir : Utiliser $O(n \log n)$ pour les grands volumes de données.

Comment fonctionne la stratégie "Diviser pour régner" ?
  1. Diviser : Découper le problème en sous-problèmes plus petits.
  2. Régner : Résoudre les sous-problèmes récursivement.
  3. Combiner : Fusionner les résultats pour obtenir la solution finale.

💡 À retenir : C'est la base du Tri Fusion et du Tri Rapide.

Chno hiya l'complexité dyal l'tri par insertion f l'meilleur cas ?
  1. L'meilleur cas howa ila kan l'tableau deja mratb.
  2. L'algorithme ghadi ydir ghir $n-1$ comparaison.
  3. Donc l'complexité hiya $O(n)$.

💡 À retenir : Le tri par insertion est très performant sur des données presque triées.

Pourquoi on utilise souvent le tri rapide en bibliothèque standard ?
  1. Il est très rapide en moyenne.
  2. Il utilise peu de mémoire supplémentaire par rapport au tri fusion.
  3. Il est facile à implémenter de manière efficace.

💡 À retenir : C'est le meilleur compromis temps/espace pour beaucoup d'applications.

Peut-on trier un tableau en O(n) ?
  1. Oui, avec des algorithmes comme le Tri par comptage (Counting Sort), mais seulement sous certaines conditions (valeurs entières dans un intervalle restreint).
  2. Pour des données générales, la borne inférieure est $O(n \log n)$.

💡 À retenir : $O(n \log n)$ est la limite théorique pour les tris basés sur les comparaisons.

✍️ Exercices type examen national

Exercice 1

Soit un tableau $T = [5, 2, 9, 1, 5, 6]$. Appliquer manuellement l'algorithme de tri par sélection et donner l'état du tableau après chaque itération.

Voir la correction détaillée : inscription gratuite

Exercice 2

Écrire l'algorithme de recherche dichotomique en pseudo-code.

Voir la correction détaillée : inscription gratuite

Exercice 3

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

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique 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 Algorithmique

Introduction à l'algorithmique et complexitéStructures de données linéaires : Listes, Piles et FilesRécursivité et méthodes de conception d'algorithmesArbres binaires et arbres de rechercheStructures de données avancées : Tas (Heaps) et Files de prioritéTables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrantsProgrammation dynamiqueAlgorithmes gloutonsIntroduction à la théorie de la complexité (P vs NP)