CODEWITHSUNDEEP
pythonstack-overflowquicksorttail-recursion
84danie
84danie

Reputation: 95

My quicksort hangs for list of size 2^13

I've written a quicksort function in python as follows.

def quickSort1(A,p,q):
    if p < q:
        pivotIndex = partition(A,p,q)
        quickSort1(A,p,pivotIndex-1)
        quickSort1(A,pivotIndex+1,q)
def partition(A,first, last):
    pivot = A[first]
    tooBig = first+1
    tooSmall = last
    while True:
        while tooBig<=last and A[tooBig]<pivot:
            tooBig+=1
        while tooSmall>first and A[tooSmall]>pivot:
            tooSmall-=1
        if tooBig < tooSmall:
            temp = A[tooBig]
            A[tooBig] = A[tooSmall]
            A[tooSmall] = temp
        else:
            break
    A[first] = A[tooSmall]
    A[tooSmall] = pivot
    return tooSmall

I'm testing the algorithm's execution time with varying sizes of lists (from 2 to 2^16). For example,

n = 2**13
s = [random.randint(-65536,65536) for i in range(n)]
#Begin Regular Quick Sort test with unsorted list
setup = '''
gc.enable()
from __main__ import quickSort1
from __main__ import n
from __main__ import s
            '''
 average = sum(timeit.Timer('A=s[:]; quickSort1(A,0,len(A)-1)',setup = setup).repeat(1,10))/10

I've verified that the algorithm works correctly for smaller sizes, but once I reach 2^13, the program hangs. I've tried doing sys.setrecursionlimit(2**30), but this doesn't change anything. Is there something wrong with my algorithm?

Upvotes: 1

Views: 42

Answers (1)

Prune
Prune

Reputation: 77837

Yes, there's an error in your logic. If partition receives a sub-list in which A[tooBig] == A[tooSmall], then both of your while loop conditions are False from the start, and the if swaps equal values. Nothing changes, and you're stuck in an infinite loop.

I've managed to reproduce this with 212 often enough: the problem arises when your **n gets large enough that matching endpoints is a likely occurrence.

In case it helps, here's the code I used to trace the problem -- it's all yours with a few print insertions and indent to help trace teh call depth.

indent = ""

def quickSort1(A,p,q):
    global indent
    print indent, "ENTER", p, q
    indent += "  "

    if p < q:
        pivotIndex = partition(A,p,q)
        quickSort1(A,p,pivotIndex-1)
        quickSort1(A,pivotIndex+1,q)
    indent = indent[2:]
    print indent, "LEAVE"


def partition(A,first, last):
    print indent, "  PART", first, last
    pivot = A[first]
    tooBig = first+1
    tooSmall = last
    while True:
        if abs(tooSmall-tooBig) < 10:
            print indent, tooSmall, tooBig, A[tooBig:tooSmall+1]
        while tooBig<=last and A[tooBig]<pivot:
            tooBig+=1
        while tooSmall>first and A[tooSmall]>pivot:
            tooSmall-=1
        if tooBig < tooSmall:
            temp = A[tooBig]
            A[tooBig] = A[tooSmall]
            A[tooSmall] = temp
        else:
            break
    A[first] = A[tooSmall]
    A[tooSmall] = pivot
    print indent, "  PART", tooSmall
    return tooSmall

The most common loop is when the list gets down to two equal values. Here's a longer one:

2030 2022 [-32421, -32303, -32723, -32402, -32705, -32269, -32422, -32834, -32421]

Upvotes: 1

Related Questions