Где ошибка реализации алгоритма QuickSort?

Question

[UID_B Nintendo]

import random

def quickSort(arr, start, end):
    if start >= end:  # if len(arr) < 2
        return arr
    else:
        divideIndex = partition(arr, start, end)
        quickSort(arr, start, divideIndex - 1)
        quickSort(arr, divideIndex, end)

def partition(arr, head, tail):
    left = head
    right = tail
    pivot = arr[(head + tail) // 2]  # mid

    while right >= left:
        # looking through the array from the left
        while arr[left] <= pivot:
            left = left + 1
        # looking through the array from the right
        while arr[right] > pivot:
            right = right - 1
        # found a couple of elements that can be exchanged.
        if left <= right:
            swap(arr[right], arr[left])
            # move the left and right wall
            left = left + 1
            right = right - 1
    # return one elements if not found a couple
    return left

def swap(arr1, arr2):
    temp = arr1
    arr1 = arr2
    arr2 = temp

# Generator random variables
deck = list(range(50))
random.shuffle(deck)


start = 0
end = len(deck) - 1
print(quickSort(deck, start, end))

При запуске кода пишет мне это: RecursionError: maximum recursion depth exceeded in comparison

Comments

[res2001]

В детали не вдавался, но ошибка говорит о слишком большом уровне рекурсий. Это стандартная недостаток рекурсивных функций. Перепешите алгоритм в итерационном стиле, без рекурсии.

Answer 1

[Kpoxa]

https://stackoverflow.com/questions/3323001/what-i...

Answer 2

[Андрей]

Проверьте еще раз условия циклов:
1.

while arr[left] <= pivot:
            left = left + 1

Что будет с переменной left, если массив состоит из одних и тех же чисел? Например, попробуйте вызвать print(quickSort([1, 1, 1, 1], 0, 3))
2. Функция swap работает не совсем так, как вы ожидаете: в неё передаются числа, которые внутри функции становятся локальными переменными, соответственно, присваивания, которые в ней происходят, отражаются только на этих локальных перменных, но не исходном массиве. Попробуйте 1) "заинлайнить" функцию в место вызова (заменить место вызова на тело функции), или 2) перепишите функцию так, чтобы она принимала на вход массив arr, и два индекса, и производила обмен над массивом (подробнее про это можно почитать https://docs.python.org/3/faq/programming.html#how... , https://stackoverflow.com/questions/986006/how-do-... )

Comments

[UID_B Nintendo]

Да кстати я хотел тогда еще кое что уточнить. Как правильно передать индексы массива если я перепишу код ?

array = [6,8,9,4,5,7,1,10,11]
start = 0
end = len(array) - 1
print(quickSort(array, start, end))