# Why does this code throw an error - "Python stopped working"?

0

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)")
``````

Process finished with exit code -1073741571 (0xC00000FD)

python
sorting
quicksort
asked on Stack Overflow May 29, 2019 by TimeseriesAnalysis • edited May 29, 2019 by Prasang Srivastava

0

You've initially run up against the recursion limit, and (mostly) sensibly raised it in response.

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

The array you're sorting has 6000 elements. At the first level of recursion, you call `quicksort(array(low, pivot))`, which splits your array and calls it again on an array with about 3000 elements. This carries on until you're sorting array[0:2], with about 3000 frames on the stack. That final call returns, freeing a frame from the stack, and then the second call to `quicksort(array, pivot + 1, high)` happens, filling it up again.

If we've reasoned correctly so far, it seems as if the stack grows to about 3k frames deep, bounces back and forth down to there (+/- calls to `help()`), before finally unwinding all the way back when you get your sorted array back.

If this is the case, then it seems the practical recursion limit, defined by the amount of frames you can fit in the stack, is something less than 3000.

In theory, any recursion algorithm can be solved iteratively, so you could try rewriting `quicksort`. If you're curious about the maximum recursion depth on your machine and os, you could pass an integer argument that you increment and print in every call. After it blows up, the highest number printed will be your actual recursion depth limit.

`setrecursionlimit()` lets you take matters into your own hands with the stack. With great power comes great responsibility.

answered on Stack Overflow May 29, 2019 by Mike
0

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]
``````
answered on Stack Overflow May 29, 2019 by rcgldr

User contributions licensed under CC BY-SA 3.0