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().
Cette activité fait partie du cours
Structures de données et algorithmes en Python
Exercice interactif pratique
Essayez cet exercice en complétant ce code d’exemple.
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer