Реалізація алгоритму quicksort
У цій вправі ви реалізуєте алгоритм quicksort для сортування списку чисел.
Спочатку ви реалізуєте функцію partition(), яка повертає індекс опорного елемента після обробки списку так, щоб усі елементи ліворуч від опорного були меншими за нього, а всі елементи праворуч — більшими.
На другому кроці ви реалізуєте функцію quicksort(), яка викликатиме функцію partition().
Ця вправа є частиною курсу
Структури даних і алгоритми в Python
Інтерактивна практична вправа
Спробуйте виконати цю вправу, доповнивши цей зразок коду.
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