If I want to sort via the following QuickSort algorithm I get either a "RecursionError: maximum recursion depth exceeded in comparison" failure, or if I set the recursion limit much higher, Python stops working after it sortied via BubbleSort with (Process finished with exit code -1073741571 (0xC00000FD)). Does anyone have a idea, how i can fix this problem
Set recursion limit higher
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)")
A bit of introductory tracing shows the problem:
indent = ""
def quickSort(array, low, high):
global indent
# print(indent, "quickSort ENTER", low, high)
indent += " "
if (low<high):
pivot = help(array, low, high)
print(low, high, pivot)
quickSort(array, low, pivot)
quickSort(array, pivot + 1, high)
indent = indent[2:]
After seeing the stack problem, I inserted the print statement that includes the pivot. The output is
0 5999 0
1 5999 1
2 5999 2
3 5999 3
4 5999 4
5 5999 5
6 5999 6
...
994 5999 994
995 5999 995
996 5999 996
Traceback (most recent call last):
File "so.py", line 79, in <module>
quickSort(copy3, 0, len(copy3)-1)
File "so.py", line 46, in quickSort
quickSort(array, pivot + 1, high)
File "so.py", line 46, in quickSort
quickSort(array, pivot + 1, high)
File "so.py", line 46, in quickSort
quickSort(array, pivot + 1, high)
[Previous line repeated 994 more times]
File "so.py", line 43, in quickSort
pivot = help(array, low, high)
File "so.py", line 28, in help
while(array[fromhigh]>pivot):
RecursionError: maximum recursion depth exceeded in comparison
Your problem is that your pivot logic always returns the low element, which alters your algorithm to O(N^2), dying when N
is greater than your allowed stack depth.
Can you take it from there?
See this lovely debug blog for help.
Even a trivial print
will give you a lot of clues.
User contributions licensed under CC BY-SA 3.0