Exercices de programmation pour classes préparatoires
Écrire une fonction tri_rapide : int list -> int list qui trie une liste d'entiers par ordre croissant selon l'algorithme du tri rapide (quicksort).
Principe :
1. Prendre la tête de la liste comme pivot.
2. Séparer le reste de la liste en deux sous-listes : ceux strictement inférieurs au pivot, et ceux supérieurs ou égaux au pivot.
3. Trier récursivement chacune des deux sous-listes.
4. Concaténer : tri_rapide petits @ [pivot] @ tri_rapide grands.
| Appel | Résultat attendu |
|---|---|
| tri_rapide [3; 1; 4; 1; 5; 9; 2; 6] | [1; 1; 2; 3; 4; 5; 6; 9] |
| tri_rapide [] | [] |
Connectez-vous pour soumettre du code.