为什么此代码会引发错误-"Python停止工作"? [英] Why does this code throw an error - "Python stopped working"?

问题描述

在这段代码中，我想对一些随机生成的数字进行排序.如果我要对超过2000个元素进行排序，则在通过QuickSort进行排序时(在通过Bubblesort进行排序之后)，Python将停止工作，并抛出进程以退出代码-1073741571(0xC00000FD)完成".我不知道，为什么会出现这个问题.我的递归深度是扩展，所以我不认为这是问题.有谁知道我该如何解决这个问题?

In this code, I want to sort some random generated Numbers. If I want to sort more than ~2000 elements, Python stops working when sorting via QuickSort (after it sorted via Bubblesort) and throws "Process finished with exit code -1073741571 (0xC00000FD)". I dont know, why this problem occurs. My recursion depth is extendet, so I dont think this is the problem. Has anyone a idea, how I can solve this problem?

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)

Process finished with exit code -1073741571 (0xC00000FD)

推荐答案

通过在较小(或相等)部分上使用递归，然后迭代以处理较大部分，可以避免Quicksort中的堆栈溢出:

You can avoid stack overflow in quicksort by using recursion on the smaller (or equal) part, then iterating back to handle the larger part:

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

对于已经排序的数据，在帮助中最好选择中间值作为枢轴:

For already sorted data, in help it would be better to choose the middle value as pivot:

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

这篇关于为什么此代码会引发错误-"Python停止工作"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！