Using quicksort on lists >=7000 causes stack overflow

Question

I'm trying to test the computation time of multiple sorting algorithms on increasingly larger sets of data. Quicksort has a memory error when it reaches 7000.

I have set the recursion limit to 10**6 in order to combat the maximum recursion depth when using timsort

from random import randint
import time
import math
start = 1000
finish = 10000
inc = 1000
import  sys
sys.setrecursionlimit(10**6)
def generateNew(z):
    listt = []
    for o in range(z):
        listt.append(randint(0, z))
    return listt

...


def partition(arr,low,high): 
    i = ( low-1 )
    pivot = arr[high]

    for j in range(low , high): 
        if   arr[j] <= pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
def quickSort(arr,low,high): 
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 

def quickSortTimer(unsorted):
    start = time.time()
    array = unsorted
    quickSort(array,0,len(array)-1) 

    end = time.time()
    print("Quick Sort: "+str(end - start))


...


def runAll():


    for h in range(start, finish+1, inc):
        print("\n\nCurrent: "+str(h))
        unsorted = generateNew(h)
        oddEvenSortTimer(unsorted)
        #stoogeSortTimer(unsorted)
        gnomeSortTimer(unsorted)
        #bogoSortTimer(unsorted)
        binaryInserionSortTimer(unsorted)
        pancakeSortTimer(unsorted)
        bitonicSortTimer(unsorted)
        cocktailSortTimer(unsorted)
        cycleSortTimer(unsorted)
        pigeonholeSortTimer(unsorted)
        combSortTimer(unsorted)
        timSortTimer(unsorted)
        shellSortTimer(unsorted)
        bucketSortTimer(unsorted)
        radixSortTimer(unsorted)
        heapSortTimer(unsorted)
        quickSortTimer(unsorted)
        mergeSortTimer(unsorted)
        selectionSortTimer(unsorted)
        insertionSortTimer(unsorted)
        bubbleSortTimer(unsorted)

I expect the program to continue running but instead I get the error: MemoryError: Stack overflow. This question got marked as a duplicate of another question explaining how to increase the recursion depth, but this is another error. I want to maintain the recursion depth but avoid the stack overflow error.

The "partition" function looks weird to me. You take a pivot element, compare it to a second element and swap second and a third element (where second and third can be the same). — Michael Butscher, May 27 '19 at 11:51

score 1 · Answer 1 · answered May 28 '19 at 07:24

To avoid stack overflow, use recursion on the smaller (or equal) part, then iterate back to handle the larger part.

def quicksort(a, lo, hi):
    while(hi - lo > 0):
        pivot = a[hi]
        i = lo
        for j in xrange(lo, hi):
            if a[j] <= pivot:
                a[i],a[j] = a[j],a[i]
                i += 1
        a[i],a[hi] = a[hi],a[i]
        if(i - lo <= hi - i):
            quicksort(a, lo, i-1)
            lo = i+1
        else:
            quicksort(a, i+1, hi)
            hi = i-1

Using quicksort on lists >=7000 causes stack overflow

1 Answers1