Implement in Python the partition algorithm – i.e. def partition(input_list, start, end, pivot_position)
– that takes a list and the positions of the first and last elements in the list to consider as inputs, and redistributes all the elements of a list having position included between start
and end
on the right of the pivot value input_list[pivot_position]
if they are greater than it, and on its left otherwise. In addition, the new position where the pivot value is now stored will be returned by the algorithm. For instance, considering my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
, the execution of partition(my_list, 1, 4, 1)
changes my_list
as follows: list(["The Graveyard Book", "American Gods", "Coraline", "Neverwhere", "Good Omens"])
and 2 will be returned (i.e. the new position of "Coraline"
). Note that "The Graveyard Book"
has not changed its position in the previous execution since it was not included between the specified start and end positions (i.e. 1 and 4 respectively).
Accompany the implementation of the function with the appropriate test cases.