Algorithmes de tri
Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.
À propos de ce thème
Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.
Questions clés
- Comment fonctionne le tri par sélection ?
- Quelle est la différence de principe avec le tri par insertion ?
- Comment démontrer qu'un algorithme de tri se termine toujours ?
Plus dans Algorithmique
Parcours séquentiel et recherche
Écrire des algorithmes pour parcourir un tableau à la recherche d'un élément, d'un extremum ou pour calculer une moyenne.
2 methodologies
Recherche dichotomique
Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.
2 methodologies
Algorithmes gloutons
Résoudre des problèmes d'optimisation à l'aide d'algorithmes gloutons, en s'appuyant sur l'exemple classique du problème du rendu de monnaie.
2 methodologies