QuickSort doesnt work with more than ~2000 elements. Why?

Question

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

If recursion depth is the problem, then the usual solution ([as mentioned in this answer](https://stackoverflow.com/a/70631/2648811)) is to use a different algorithm, such as mergesort (which can potentially tolerate a larger recursion depth) or heapsort (which isn't recursive at all, and is still O(nlogn)). Your choice of pivot may also affect things (picking a random element, or picking the middle between the first/middle/last elements is often better than just picking the first element) — Green Cloak Guy, May 29 '19 at 16:24
This is a duplicate of the same code posted by the OP with this [answer](https://stackoverflow.com/questions/56359624/why-does-this-code-throw-an-error-python-stopped-working/56364006#56364006) . — rcgldr, May 29 '19 at 21:33

score 1 · Answer 1 · answered May 29 '19 at 16:31

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.

QuickSort doesnt work with more than ~2000 elements. Why?

1 Answers1