1. Apprendre
    2. /
  2. Cours
    3. /
  3. Structures de données et algorithmes en Python
Connected

Exercice

Implémenter l'algorithme de tri rapide (quicksort)

Dans cet exercice, vous allez implémenter l'algorithme de tri rapide (quicksort) pour trier une liste de nombres.

Dans la première étape, vous allez implémenter la fonction partition(), qui retourne l'indice du pivot après avoir transformé la liste de sorte que tous les éléments à gauche du pivot soient inférieurs au pivot et que tous les éléments à droite du pivot soient supérieurs au pivot.

Dans la deuxième étape, vous allez implémenter la fonction quicksort(), qui appellera la fonction partition().

Instructions 1/2

undefined XP
    1
    2
  • Itérez jusqu'à ce que la valeur pointée par left_pointer soit supérieure à pivot ou que left_pointer soit supérieur à last_index.
  • Échangez les valeurs des éléments situés aux positions left_pointer et right_pointer.