Реализация алгоритма быстрой сортировки
В этом упражнении вы реализуете алгоритм быстрой сортировки для упорядочивания списка чисел.
На первом шаге вы реализуете функцию 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