Быстрая сортировка Python TypeError

Question

Ниже приведены ошибки, которые выдает мой код:

 File "python", line 39, in <module>
  File "python", line 8, in quicksort
  File "python", line 8, in quicksort
TypeError: unsupported operand type(s) for -: 'NoneType' and 'int'

Ниже приведен мой код для быстрой сортировки:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def quicksort(arr, beg, end):
    if beg < end:
        pivot = partition(arr, beg, end)
        quicksort(arr, beg, pivot - 1)
        quicksort(arr, pivot + 1, end)

def partition(arr, beg, end):
    left = beg
    right = end
    loc = beg
    while arr[loc] <= arr[right] and loc != right:
        right = right - 1
    if loc == right:
        return loc
    elif arr[loc] > arr[right]:
        (arr[loc], arr[right]) = (arr[right], arr[loc])
        loc = right

    while arr[loc] >= arr[left] and loc != left:
        left = left + 1
    if loc == left:
        return loc
    elif arr[loc] < arr[left]:
        (arr[loc], arr[left]) = (arr[left], arr[loc])
        loc = left

y = [9,7,5,1,5]
quicksort(y, 0, 4)
print(y)

Answer 1

Из функции partition вы ничего не возвращаете. И вы присвоили это переменной pivot. Вот в чем проблема. Следите за значением, которое вы должны вернуть.

Answer 2

Вы не можете вычесть 2 переменные из разных типов (None и int).
Вы получили None, потому что не все пути функции partition возвращают что-то.
В конце я добавил оператор return, который для меня наиболее логичен:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def quicksort(arr, beg, end):
    if beg < end:
        pivot = partition(arr, beg, end)
        quicksort(arr, beg, pivot - 1)
        quicksort(arr, pivot + 1, end)

def partition(arr, beg, end):
    left = beg
    right = end
    loc = beg
    while arr[loc] <= arr[right] and loc != right:
        right = right - 1
    if loc == right:
        return loc
    elif arr[loc] > arr[right]:
        (arr[loc], arr[right]) = (arr[right], arr[loc])
        loc = right

    while arr[loc] >= arr[left] and loc != left:
        left = left + 1
    if loc == left:
        return loc
    elif arr[loc] < arr[left]:
        (arr[loc], arr[left]) = (arr[left], arr[loc])
        loc = left

    return loc


y = [9,7,5,1,5]
quicksort(y, 0, 4)
print(y)  # >>> [1, 5, 5, 7, 9]

Однако я не проверял правильность логики вашего кода для каждого сценария.
Вы можете проверить этот поток , чтобы увидеть реализации быстрой сортировки в python.