Почему этот код выдает ошибку - «Python перестал работать»?

Question

В этом коде я хочу отсортировать случайно сгенерированные числа. Если я хочу отсортировать более чем 2000 элементов, Python перестает работать при сортировке через QuickSort (после сортировки через Bubblesort) и выдает «Процесс завершен с кодом выхода -1073741571 (0xC00000FD)». Я не знаю, почему эта проблема возникает. Глубина рекурсии у меня слишком большая, поэтому я не думаю, что это проблема. У кого-нибудь есть идеи, как мне решить эту проблему?

import time
import random
from sys import setrecursionlimit
setrecursionlimit(1000000)

#------------------------------Sortieralgorithmen-----------------------------------------------
#-----------------------------------------------------------------------------------------------

def bubbleSort(array):

    length = len(array)

    for sorted in range(length):

        for j in range(0, length-sorted-1):
            if array[j] > array[j+1] :
                array[j], array[j+1] = array[j+1], array[j]



def help(array, low, high):
    pivot = array[low]
    fromhigh = high
    fromlow = low
    while True:
        while(array[fromhigh]>pivot):
            fromhigh = fromhigh-1
        while(array[fromlow]<pivot):
            fromlow = fromlow+1
        if(fromlow<fromhigh):
            array[fromlow], array[fromhigh] = array[fromhigh], array[fromlow]
        else:
            return fromhigh


def quickSort(array, low, high):
   if (low<high):
       pivot = help(array, low, high)
       quickSort(array, low, pivot)
       quickSort(array, pivot + 1, high)




#--------------------------------Zeitmessung-----------------------------------------------------
#------------------------------------------------------------------------------------------------

numb_elements = 6000

sortedarray = []
for i in range (0,numb_elements):
    sortedarray.append(i)

notsortedarray = random.sample(range(0,numb_elements),numb_elements)

copy1 = sortedarray.copy()
before = time.time()
bubbleSort(copy1)
after = time.time()
total = after-before
print("Bubblesort sortiertes Array:\t\t" + str(total))

copy2 = notsortedarray.copy()
before = time.time()
bubbleSort(copy2)
after = time.time()
total = after-before
print("Bubblesort nicht sortiertes Array:\t" + str(total))

copy3 = sortedarray.copy()
before = time.time()
quickSort(copy3, 0, len(copy3)-1)
after = time.time()
total = after-before
print("QuickSort sortiertes Array:\t\t\t" + str(total))

copy4 = notsortedarray.copy()
before = time.time()
quickSort(copy4, 0, len(copy4)-1)
after = time.time()
total = after-before
print("QuickSort nicht sortiertes Array:\t" + str(total)+"\t (Worst Case)")

Процесс завершен с кодом выхода -1073741571 (0xC00000FD)

Answer 1

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

def quickSort(array, low, high):
   while (low<high):
       pivot = help(array, low, high)
       if(pivot - low < high - pivot):
           quickSort(array, low, pivot)
           low = pivot+1
       else:
           quickSort(array, pivot + 1, high)
           high = pivot

Для уже отсортированных данных в справке это будетЛучше выбрать среднее значение в качестве точки разворота:

    pivot = array[(low+high)//2]

Answer 2

Вы изначально столкнулись с пределом рекурсии и (в основном) разумно подняли его в ответ.

def quickSort(array, low, high):
   if (low<high):
       pivot = help(array, low, high)
       quickSort(array, low, pivot)
       quickSort(array, pivot + 1, high)

Массив, который вы сортируете, содержит 6000 элементов. На первом уровне рекурсии вы вызываете quicksort(array(low, pivot)), который разбивает ваш массив и вызывает его снова в массиве с около 3000 элементов. Это продолжается до тех пор, пока вы не сортируете массив [0: 2], в стеке около 3000 кадров. Этот последний вызов возвращается, освобождая кадр из стека, а затем происходит второй вызов quicksort(array, pivot + 1, high), заполняя его снова.

Если мы до сих пор правильно рассуждали, кажется, что стек увеличивается примерно до 3 тыс. Кадров в глубину, отскакивает туда-сюда (+/- вызывает help()), прежде чем, наконец, развернуть все обратно когда вы вернете отсортированный массив.

Если это так, то кажется, что практический предел рекурсии, определяемый количеством кадров, которые вы можете поместить в стек, составляет что-то меньше 3000.

Теоретически, любой алгоритм рекурсии может быть решен итеративно, поэтому вы можете попробовать переписать quicksort. Если вас интересует максимальная глубина рекурсии на вашем компьютере и ОС, вы можете передать целочисленный аргумент, который вы увеличиваете и печатаете при каждом вызове. После того, как он взорвется, наибольшее напечатанное число будет вашим фактическим пределом глубины рекурсии.

setrecursionlimit() позволяет взять вещи в свои руки со стеком. С великой силой приходит большая ответственность.