Что не так с этой реализацией алгоритма быстрой сортировки? Ошибка, являющаяся RecursionError - PullRequest
Новая
       9

Что не так с этой реализацией алгоритма быстрой сортировки? Ошибка, являющаяся RecursionError

0 голосов
/ 09 марта 2020 
def quicksort(array):
    print(array)
    n = 0
    pivot = len(array) - 1
    while n < pivot:
        if array[pivot] > array[n]:
            n+=1
        elif array[pivot] <= array[n]:
            array[n],array[pivot-1] = array[pivot-1], array[n]
            array[pivot],array[pivot-1] = array[pivot-1], array[pivot]
            pivot -= 1
    if len(array[:pivot]) >1:
        array[:pivot] = quicksort(array[:pivot])
    if len(array[pivot+1:])> 1:
        array[pivot+1:] = quicksort(array[pivot+1:])
    return array

test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print(quicksort(test))

вызывает следующую ошибку: 

Error: Traceback (most recent call last):
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 18, in <module>
    print(quicksort(test))
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 12, in quicksort
    array[:pivot] = quicksort(array[:pivot])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  [Previous line repeated 987 more times]
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 3, in quicksort
    pivot = len(array) - 1
RecursionError: maximum recursion depth exceeded while calling a Python object

Ответы [ 2 ]

1 голос
/ 09 марта 2020 
def quicksort(array):
print(array)
n = 0
pivot = len(array) - 1
while n < pivot:
    if array[pivot] > array[n]:
        n+=1
    elif array[pivot] <= array[n]:
        array[n],array[pivot-1] = array[pivot-1], array[n]
        array[pivot],array[pivot-1] = array[pivot-1], array[pivot]
        pivot -= 1
if len(array[:pivot]) >1:
    array[:pivot] = quicksort(array[:pivot])
if len(array[pivot:])> 1:
    array[pivot:] = quicksort(array[pivot:])
return array

test = [19, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print(quicksort(test))

М - это правильно! Я попробовал этот модифицированный код, и он работает на массиве с различными элементами. Вывод: 

[19, 4, 1, 3, 9, 20, 25, 6, 21, 14]
[6, 4, 1, 3, 9]
[6, 4, 1, 3]
[3, 4, 6]
[3, 4]
[14, 25, 20, 21, 19]
[19, 20, 21, 25]
[19, 20, 21]
[19, 20]
[1, 3, 4, 6, 9, 14, 19, 20, 21, 25]
  • Если вам нужна быстрая сортировка, работающая с массивом с повторяющимися элементами, вам придется разбить ее на 3 (вместо 2) подмассива {{Xi}, {Xk}, {Xj}}, где {Xi} меньше, чем пивот, {xk}=pivot и {Xj} > pivot.
1 голос
/ 09 марта 2020 
def quicksort(array):
    print(array)
    n = 0
    pivot = len(array) - 1
    while n < pivot:
        if array[pivot] > array[n]:
            n+=1
        elif array[pivot] <= array[n]:
            array[n],array[pivot-1] = array[pivot-1], array[n]
            array[pivot],array[pivot-1] = array[pivot-1], array[pivot]
            pivot -= 1
    if len(array[:pivot]) >1:
        array[:pivot] = quicksort(array[:pivot])
    if len(array[pivot+1:])> 1:
        array[pivot+1:] = quicksort(array[pivot+1:])
    return array

test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print(quicksort(test))

Это было просто исключение пивота из подмассивов. Таким образом, массив [pivot:] становится массивом [pivot + 1:]

...