Implémentation de l'algorithme de tri sélectif
Dans cet exercice, vous allez implémenter l'algorithme de tri sélectif pour trier une liste de nombres.
Dans un premier temps, vous implémenterez la fonction partition(), qui renvoie l'indice du pivot après avoir traité la liste de nombres de manière à ce que tous les éléments situés à gauche du pivot soient inférieurs au pivot et que tous les éléments situés à droite du pivot soient supérieurs au pivot.
Dans la deuxième étape, vous implémenterez la fonction quicksort(), qui appellera la fonction partition().
Cet exercice fait partie du cours
Structures de données et algorithmes en Python
Exercice interactif pratique
Essayez cet exercice en complétant cet exemple de code.
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