Получение ошибки: максимальная глубина рекурсии превышена в сравнении - PullRequest
Новая
       45

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

1 голос
/ 20 апреля 2020

Я пытался написать алгоритм быстрой сортировки, используя схему разбиения Hoare. Я почти уверен, что моя функция Partition правильная. Я использую переменную 'Swaps', чтобы указать движение левого поворота вправо и движение правого поворота влево. Функция Sort работает с другим алгоритмом разделения, так что я думаю, что это тоже хорошо. Все же я получаю ошибку. 

inp=[2,3,6,3,9,7,8,0,5]

#Swap Function
def Swap(List, i, j):
    temp=List[i]
    List[i]=List[j]
    List[j]=temp


#QuickSort Function
def QSort(List, Start, End):
    if Start < End:

        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

    return List



#Partition Function
def Partition (List, Start, End):
    Swaps=0
    PIStart=Start #PI = Pivot Index
    PIEnd=End 

    for i in range(Start, End):
        if List[PIStart] > List[PIEnd]:
            Swap(List, PIStart, PIEnd)
            Swaps=Swaps+1       
        if Swaps % 2 ==0:
            PIStart=PIStart+1
        else:
            PIEnd=PIEnd-1

    return PIEnd

print(QSort(inp, 0, 8))

1 Ответ

1 голос
/ 20 апреля 2020

Посмотрите в этих двух местах ... 

# QSort ...
        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

# Partition
        if Swaps % 2 ==0:
            PIStart=PIStart+1
        else:
            PIEnd=PIEnd-1

Если у вас есть четное количество перестановок в любом разделе, то PIEnd не изменится, и ваша косвенная рекурсия в QSort будут придерживаться тех же аргументов. Ваша первая лоу-половина рекурсия делает это. Пересмотрите свою логику c. Для начала вы должны , а не зависеть от глобальных переменных для решения.

Вот как я снабдил ваш код рекурсивной трассировкой: 

call_count = 0
indent = ""


#QuickSort Function
def QSort(List, Start, End):
    global call_count, indent
    indent += "  "
    call_count += 1
    print(indent, "ENTER QSort", Start, End, List)

    if call_count > 2 * len(inp):
        print(indent, "Too many calls")
        exit(1)

    if Start < End:

        PIEnd=Partition(List, Start, End)

        QSort(List,Start,PIEnd)
        QSort(List,PIEnd+1,End)

    print(indent, "ENTER QSort", Start, End, List)    
    indent = indent[2:]

    return List

Вывод: 

   ENTER QSort 0 8 [2, 3, 6, 3, 9, 7, 8, 0, 5]
     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
         ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
           ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
             ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
               ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                 ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                   ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                         ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                           ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                             ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                               ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                 ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                   ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                     ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                       ENTER QSort 0 4 [2, 3, 0, 3, 5, 7, 8, 9, 6]
                                       Too many calls
...