CODEWITHSUNDEEP
pythonalgorithmsortingquicksort
JDS
JDS

Reputation: 16978

QuickSort in Python - program hangs for larger input sizes?

Pretty confused about this because I've verified correct logical output for small enough testcases (N = 20). I try doing N = 10,000 numbers and the program just hangs and I don't understand why... I've implemented the algorithm as simply as I can.

Also, calling sorted(data) on my N = 10k list seems to work almost instantly. So I'm convinced my algorithm just gets stuck somewhere.

Here is the code: 

def QuickSort(array):
    qsort(array, 0, len(array))


def qsort(arr, left, right):
    if ((right - left) < 2):
        return

    pivotIndex = choosePivot0(arr, left, right)

    newPivotIndex = partition(arr, pivotIndex, left, right)

    qsort(arr, 0, newPivotIndex)
    qsort(arr, newPivotIndex + 1, right)

def partition(arr, pivotIndex, left, right):
    swap(arr, pivotIndex, left)
    pivot = arr[left]
    i = left + 1
    for j in range(left+1, right):
        if (arr[j] < pivot):
            swap(arr, i, j)
            i = i + 1

    swap(arr, left, i-1) #put pivot back where it belongs
    #cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons
    return (i-1) #give back where the pivot resides



def swap(array, i, j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def choosePivot0(array, left, right):
    return randint(left, right-1) #random

So I'm pretty lost as to why this could be happening. Thanks for any help.

Upvotes: 5

Views: 1060

Answers (3)

NedStarkOfWinterfell
NedStarkOfWinterfell

Reputation: 5153

Python often hangs for deep recursive functions, sometimes it just terminates the current session (if you are trying it out in IDLE), and starts a fresh session without giving any output at all. Try this: import sys; sys.setrecursionlimit(2**30), this may help, though not always.

Upvotes: 2

Maksim Skurydzin
Maksim Skurydzin

Reputation: 10541

There seems to be a typo in the following line:

qsort(arr, 0, newPivotIndex)

I think it should be like this. 

qsort(arr, left, newPivotIndex)

Otherwise the function will work somehow only for some of the input data sets. That is why the algorithm gets stuck.

Upvotes: 5

AJP
AJP

Reputation: 28463

Note: I haven't check your algorithm so there maybe be a problem with it / python may not like it for some reason but: Quick sort will approximately improve sorting time from N^2 to N log(N), but maybe as bad as N^2 depending on input data. With optimal data, N=10,000 compared to N=20, would be a factor of 40,000/26 = 1538 times slower. Perhaps it's just processing?

With worst case data it will be 100,000,000 / 400 = 25,000 times slower. What's your data?

Upvotes: 2

Related Questions