Leçon 5 sur 5
Complexité et tris efficaces : tri fusion et tri rapide
Je sais évaluer la complexité d'un algorithme avec la notation O, expliquer pourquoi les tris par insertion et par sélection deviennent inutilisables sur de grandes données, et programmer le tri fusion et le tri rapide en justifiant leur coût en O(n log n).
- 1 h 30
- 6 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Utiliser les notations O, Ω et Θ et classer les complexités usuelles
- Estimer un temps d'exécution à partir d'une complexité
- Programmer le tri fusion et établir sa relation de récurrence
- Programmer le tri rapide avec une partition, et analyser son meilleur et son pire cas
- Choisir un tri selon le contexte (stabilité, mémoire, données presque triées)
Avant de commencer : Leçon 3 (récursivité) ; Algorithmique (L1 : tri par sélection, tri par insertion, recherche dichotomique).
1Je découvre
Après la publication des résultats d'un concours national, une équipe d'étudiants de Conakry doit classer plusieurs centaines de milliers de candidats par note décroissante pour un site de consultation. Leur premier programme utilise le tri par insertion vu en L1. Sur 1 000 candidats de test, il répond en une fraction de seconde. Sur le fichier complet, il tourne encore au bout d'une heure, et le groupe électrogène de la salle informatique doit être éteint.
Un camarade remplace la fonction de tri par un tri fusion de vingt lignes : le classement complet s'affiche en quelques secondes, sur la même machine.
Ce n'est pas l'ordinateur qui a changé, c'est l'algorithme.
Comment mesurer l'efficacité d'un algorithme indépendamment de la machine, et comment fonctionnent les tris qui restent rapides sur des millions de données ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.
Voir toutes les leçons de Algorithmique avancée et structures de données
Signaler une erreur dans cette leçon
Toutes les leçons de Algorithmique avancée et structures de données