Quicksort algorithm Python error

Question

I am trying to implement Quicksort using Python. This is my code:

import random

def quickSort(lst):
    randomIndex = random.randint(0,len(lst)-1)
    pivot = lst[randomIndex]
    greater = []
    less = []
    equal = []
    if len(lst) > 1:
        for num in lst:
            if num > pivot:
                greater.append(num)
            elif num == pivot:
                equal.append(num)
            else:
                less.append(num)
        return quickSort(less)+equal+quickSort(greater)
    else:
        return lst

def main():
    lst = [1000000,100000,1000,10000,100,10]
    sortedLst = quickSort(lst)
    print("Quicksorted List: ", sortedLst)

main()

How come when I run my code, it says that it runs into this error:

ValueError: empty range for randrange() (0,0, 0)

error is pretty self-explonatory. You call random on empty range, thus at some point your code calls quicksort([]), and you try to get randomIndex/pivot even when the list is empty — lejlot
– lejlot, Commented Jan 31, 2016 at 19:05
It's most likely because either greater or less has one element in them. So when you set randomIndex to be a range from 0 to the length of the list, you get random.randint(0, 0). I'd recommend adding a print command before your return statement to see what those lists look like. — tblznbits
– tblznbits, Commented Jan 31, 2016 at 19:05

lejlot · Accepted Answer · 2016-01-31 19:06:22Z

2

The only problem is that you try to select randomIndex even, when lst is empty, just move your initializations into if condition where you are sure that they are non empty

import random

def quickSort(lst):
    if len(lst) > 1:
        randomIndex = random.randint(0,len(lst)-1)
        pivot = lst[randomIndex]
        greater = []
        less = []
        equal = []
        for num in lst:
            if num > pivot:
                greater.append(num)
            elif num == pivot:
                equal.append(num)
            else:
                less.append(num)
        return quickSort(less)+equal+quickSort(greater)
    else:
        return lst

def main():
    lst = [1000000,100000,1000,10000,100,10]
    sortedLst = quickSort(lst)
    print("Quicksorted List: ", sortedLst)

main()

answered Jan 31, 2016 at 19:06

lejlot

67k9 gold badges138 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Quicksort algorithm Python error

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related