Как исправить быструю сортировку?

Question

[Rohan Shwtty]

алгоритмом быстрой сортировки с хвостовой рекурсией, однако код, похоже, сталкивается с бесконечной рекурсией, что приводит к переполнения стека для огромных наборов данных.

код:

def quick_sort_tail_recursive(arr, low, high):
    while low < high:
        pivot_index = partition(arr, low, high)

        # Tail recursion on the smaller partition
        if pivot_index - low < high - pivot_index:
            quick_sort_tail_recursive(arr, low, pivot_index - 1)
            low = pivot_index + 1
        else:
            quick_sort_tail_recursive(arr, pivot_index + 1, high)
            high = pivot_index - 1

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Example usage
my_array = [38, 27, 43, 3, 9, 82, 10]
quick_sort_tail_recursive(my_array, 0, len(my_array) - 1)
print(my_array)

Однако, когда выполняю код с образцом my_array, получаю проблему переполнения стека, что есть проблема с тем, как обрабатываю хвостовую рекурсию и обновляю низкие и высокие переменные.

Comments

[Wataru]

Короткая поограмма же - ну отладьте же ее. Добавьте, например, вывод имени ипараметров в начало каждой функции. Запустите и смотрите, что происходит.

Answer 1

[Rsa97]

В вашем коде нет хвостовой рекурсии. При хвостовой рекурсии вызов рекурсивной функции - последняя команда в этой функции перед выходом из неё. У вас же эта функция вызывается в цикле и выполнение после вызова продолжается.