Exercices de programmation pour classes préparatoires
Écrire une fonction tri_rapide(lst) qui trie une liste d'entiers en utilisant l'algorithme du tri rapide (quicksort) et renvoie une nouvelle liste triée.
Le principe du tri rapide est le suivant : 1. Si la liste contient 0 ou 1 élément, elle est déja triée. 2. Choisir un élément pivot (par exemple le premier élément). 3. Partitionner les autres éléments en deux sous-listes : ceux inférieurs ou égaux au pivot, et ceux strictement supérieurs au pivot. 4. Trier récursivement les deux sous-listes. 5. Concaténer : sous-liste gauche triée + [pivot] + sous-liste droite triée.
La liste d'origine ne doit pas etre modifiée.
| Appel | Résultat attendu |
|---|---|
| tri_rapide([3, 6, 8, 10, 1, 2, 1]) | [1, 1, 2, 3, 6, 8, 10] |
| tri_rapide([5]) | [5] |
Connectez-vous pour soumettre du code.