Как реализовать быструю сортировку с помощью рекурсии

Question

Я практикую использование рекурсии для реализации алгоритма быстрой сортировки.Я получаю сообщение об ошибке:

RecursionError: превышена максимальная глубина рекурсии в сравнении

Вот ошибка:

In [2]: run quicksort.py
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
~/Desktop/algo/quicksort.py in <module>()
     27 
     28 test = QuickSort()
---> 29 print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))

~/Desktop/algo/quicksort.py in partition(array, start, end)
     20     def partition(array, start, end):
     21         if start < end:                       # this is enough to end recursion
---> 22             pos = QuickSort.partition(array, start, end)
     23             QuickSort.quickSort(array, start, pos - 1)
     24             QuickSort.quickSort(array, pos + 1, end)

... last 1 frames repeated, from the frame below ...

~/Desktop/algo/quicksort.py in partition(array, start, end)
     20     def partition(array, start, end):
     21         if start < end:                       # this is enough to end recursion
---> 22             pos = QuickSort.partition(array, start, end)
     23             QuickSort.quickSort(array, start, pos - 1)
     24             QuickSort.quickSort(array, pos + 1, end)

RecursionError: maximum recursion depth exceeded in comparison

Вот мой текущийкод (я использую класс, чтобы другие люди могли знать, какой алгоритм я реализую):

class QuickSort:
    def __init__(self):
        self.name = "Quick Sort"
    @staticmethod
    def quickSort(arr, start, end):
        pivot = arr[end]
        i = start-1
        for x in range(start, end):
            if arr[x] > pivot:
                continue
            else:
                i += 1
                arr[i],arr[x] = arr[x],arr[i]
        for y in range(end, i + 1, -1):
            arr[y] = arr[y-1]
        arr[i + 1] = pivot
        return arr.index(pivot)
    @staticmethod
    def partition(array, start, end):
        if start < end:  # this is enough to end recursion
            pos = QuickSort.partition(array, start, end)
            QuickSort.quickSort(array, start, pos - 1)
            QuickSort.quickSort(array, pos + 1, end)

test = QuickSort()
print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))

Так что здесь «quickSort» в основном выполняет первую операцию.После этого «разбиение» будет использовать рекурсию для решения проблемы.

Answer 1

quickSort должен быть вызывающим разделом (по сравнению с разделением вызывающей быстрой сортировки). Пример кода одиночной функции, с кодом раздела, включенным в функцию быстрой сортировки. Этот пример также ограничивает пространство стека до O (log (n)), используя только рекурсию для меньшей части и итерацию (цикл) для большей части. В худшем случае сложность времени все еще равна O (n ^ 2).

class QuickSort:
    def __init__(self):
        self.name = "Quick Sort"
    @staticmethod
    def quickSort(a, lo, hi):
        while(lo < hi):
            pivot = a[hi]             # Lomuto partition
            i = lo
            for j in range(lo, hi):
                if a[j] < pivot:
                    a[i],a[j] = a[j],a[i]
                    i += 1
            a[i],a[hi] = a[hi],a[i]   # swap pivot to a[i]
            # recurse on smaller part, iterate on larger part
            if(i - lo <= hi - i):
                QuickSort.quickSort(a, lo, i-1)
                lo = i+1
            else:
                QuickSort.quickSort(a, i+1, hi)
                hi = i-1

test = QuickSort()
a = [7, 2, 1, 8, 6, 3, 5, 4]
test.quickSort(a, 0, len(a)-1)
print(a)