OCaml (option informatique) · Chapitre 9 · Exercice de TD
Tri par insertion complet
Algorithmique : les tris · niveau 2
Énoncé
Assembler tri_insertion à partir de insere, et expliquer sa terminaison.
Corrigé
let rec tri_insertion l =
match l with
| [] -> []
| x :: reste -> insere x (tri_insertion reste)On trie la queue (plus courte) puis on y insère la tête : l'appel récursif porte sur reste, strictement plus court, d'où la terminaison. La correction repose sur le fait que insere préserve le caractère trié.
Exercices semblables
- Tri fusion corrigé
- Tri rapide corrigé
- Tri par sélection en place corrigé
- Valider un tri corrigé
- Le tri par dénombrement corrigé