Реализация быстрой сортировки для сортировки списка на месте не обновляет список - PullRequest
Новая
       18

Реализация быстрой сортировки для сортировки списка на месте не обновляет список

0 голосов
/ 05 февраля 2019

Я сделал реализацию алгоритма быстрой сортировки в python3.6, используя рекурсию.Он сортирует список по возрастанию.Проблема, однако, заключается в том, что порядок элементов списка не изменяется в коде и после выполнения кода выполняется

Если вы удалите базовый случай для рекурсии и дадите сбой на максимальной достигнутой глубине рекурсии и поместите операторы печатив методе разбиения вы можете увидеть, как меняются элементы в списке 

def partition(arr, start, end):
    pivot = arr[end]
    ix = start
    for i in range(start, end):
        print("i = ", i)
        if arr[i] <= pivot:
            arr[i], arr[ix] = arr[ix], arr[i]
            ix += 1
    arr[ix], arr[end] = arr[end], arr[ix]
    return ix

def quick_sort(arr, start, end):
    if start < end: return arr
    ix = partition(arr, start, end)
    quick_sort(arr, start, ix-1)
    quick_sort(arr, ix+1, end)

arr = [2,4,7,8,9,1,3,5,6,12,32]

print("before", arr)
print("output", quick_sort(arr, 0, len(ans)-1))
print("after", arr)

OUTPUT 
before [2, 4, 7, 8, 9, 1, 3, 5, 6, 12, 32]
output [2, 4, 7, 8, 9, 1, 3, 5, 6, 12, 32]
after [2, 4, 7, 8, 9, 1, 3, 5, 6, 12, 32]

1 Ответ

0 голосов
/ 05 февраля 2019

Здесь: 

if start < end: return arr

Логика обратная.Это должно быть 

if start > end: return arr

Однако, поскольку ваша функция работает на месте, она не должна ничего возвращать, поэтому лучше сделать это 

if start > end: return

Вы увидите, что quick_sort(arr, 0, len(ans)-1) вернет None, но после вызова функции arr будет отсортирован.

...