Les algorithmes de tri et leur complexité
Fiche de révision · Numérique et sciences informatiques · 1ère
L'essentiel du cours
Chapitre 1 : Trier, pourquoi et comment ?
Trier, c'est organiser des données selon un ordre défini pour faciliter la recherche et la prise de décision.
Chapitre 2 : Tri par sélection et tri par insertion
Les tris par sélection et insertion sont simples à comprendre mais quadratiques sur de grands tableaux.
Chapitre 3 : Tri fusion et diviser pour régner
Le tri fusion a une complexité O(n log n), plus efficace que O(n²) sur les grands tableaux.
Chapitre 4 : Choisir un algorithme de tri
Choisir un tri, c'est comparer sa complexité, sa mémoire et la nature des données.
Teste-toi · 8 questions
1.Qu'est-ce qu'un algorithme de tri ?
Voir la réponseMasquer la réponse
Réponse : Une méthode pour ranger des données selon un ordre défini.
Un algorithme de tri réorganise une collection selon une relation d'ordre, par exemple croissante ou alphabétique.
2.Que fait le tri par sélection à chaque étape ?
Voir la réponseMasquer la réponse
Réponse : Il cherche le minimum de la partie non triée et l'échange avec la première place.
Le tri par sélection place successivement le plus petit élément restant à la bonne position.
3.Quel est le principe du tri par insertion ?
Voir la réponseMasquer la réponse
Réponse : Insérer chaque élément à sa place dans la partie déjà triée.
Le tri par insertion construit une partie triée en insérant chaque nouvel élément au bon endroit.
4.Quelle est la complexité du tri fusion dans le pire cas ?
Voir la réponseMasquer la réponse
Réponse : O(n log n)
Le tri fusion divise le tableau puis fusionne les sous-tableaux, ce qui conduit à une complexité en O(n log n).
5.Que signifie une complexité en O(n²) ?
Voir la réponseMasquer la réponse
Réponse : Le nombre d'opérations croît comme le carré de la taille des données.
Si n double, n² est multiplié par quatre : le coût augmente donc très vite avec la taille des données.
6.Pour un tableau de 1 000 éléments, quel algorithme est généralement le plus efficace en temps ?
Voir la réponseMasquer la réponse
Réponse : Le tri fusion, en O(n log n).
Pour de grands tableaux, O(n log n) est bien meilleur que O(n²) lorsque n devient grand.
7.Dans quel cas le tri par insertion est-il particulièrement avantageux ?
Voir la réponseMasquer la réponse
Réponse : Quand le tableau est déjà presque trié.
Sur un tableau déjà presque trié, le tri par insertion effectue peu de déplacements et peut être très rapide.
8.Pourquoi le tri fusion peut-il utiliser plus de mémoire qu'un tri par sélection ?
Voir la réponseMasquer la réponse
Réponse : Il stocke un tableau auxiliaire pour fusionner.
Le tri fusion a besoin d'espace supplémentaire pour construire les sous-tableaux et les fusionner.