Переменные в рекурсии (алгоритм quick sort)
Реализую алгоритм быстрой сортировки на Python:
def partition(lines, l, r):
x = lines[l]
j = l
for i in range(l + 1, r):
if lines[i] <= x:
j += 1
lines[j], lines[i] = lines[i], lines[j]
lines[l], lines[j] = lines[j], lines[l]
return j
def quick_sort(lines, l, r):
if l >= r:
return lines
m = partition(lines, l, r)
quick_sort(lines, l, m - 1)
quick_sort(lines, m + 1, r)
Столкнулся со следующей проблемой. Первый вызов функции partition правильно определяет индекс опорного пункта, дальше сортируем массивы слева и справа от него. Проблема в том, что переменная m, которая хранит индекс опорного пункта, изменяется после рекурсивного вызова quick_sort для левого массива, в результате чего когда вызывается quick_sort(lines, m + 1, r) границы правового массива уже потеряны.
Как сохранить значение переменной в рекурсивной функции?
Ответы (1 шт):
Ошибся в предположении. Дело оказалось не в переменной m, а в неправильных параметрах вызова функции partition. Взял их из псевдокода реализации алгоритма, но не учел, что в Python range считает до параметра stop не включая. Вот так все работает:
def quick_sort(lines, l, r):
if l >= r:
return lines
m = partition(lines, l, r)
quick_sort(lines, l, m) # ошибка была здесь
quick_sort(lines, m + 1, r)
return lines