python quicksort using rescursion

Question

I know it could be duplicated, but haven't figured out which part of my code causes recursion error. It should use less than 1000 stacks which is the recursion limit in Python.

import random

def quick_sort(arr):
    # if array is empty or has only 1 element
    # it means the array is already sorted, so return it.
    if len(arr) < 2:
        return arr
    else:
        rand_index = random.randint(0,len(arr)-1)
        pivot = arr[rand_index]
        less = []
        greater = []

        # create less and greater array comparing with pivot
        for i in arr:
            if i <= pivot:
                less.append(i)
            else:
                greater.append(i)

        return quick_sort(less) + [pivot] + quick_sort(greater)

if __name__ == "__main__":
    sample_array = [6,3,7,2,7,4,7,3,21,54,0,6,5,3,1,3]
    sorted_array = quick_sort(sample_array)
    print(sorted_array)

The error code is here below:

  File "quick_sort.py", line 24, in <module>
    sorted_array = quick_sort(sample_array)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  [Previous line repeated 991 more times]
  File "quick_sort.py", line 9, in quick_sort
    rand_index = random.randint(0,len(arr)-1)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 221, in randint
    return self.randrange(a, b+1)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 197, in randrange
    return istart + self._randbelow(width)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 231, in _randbelow
    if type(random) is BuiltinMethod or type(getrandbits) is Method:
RecursionError: maximum recursion depth exceeded while calling a Python object

Your help would be very appreciated. Thanks!

i <= pivot This condition!! When you iterate over arr, you include pivot as well. So your end result array will have more elements than the original array. — nightgaunt
– nightgaunt, Commented Dec 13, 2018 at 11:40

Max · Accepted Answer · 2018-12-13 12:07:42Z

3

You do not need to add equal numbers to less. Add it to new array and put it in middle of your return statement. Try this:

def quick_sort(arr):
    # if array is empty or has only 1 element
    # it means the array is already sorted, so return it.
    if len(arr) < 2:
        return arr
    else:
        rand_index = random.randint(0,len(arr)-1)
        pivot = arr[rand_index]
        less = []
        equal_nums = []
        greater = []

        # create less and greater array comparing with pivot
        for i in arr:
            if i < pivot:
                less.append(i)
            if i > pivot:
                greater.append(i)
            if i == pivot:
                equal_nums.append(i)

        return quick_sort(less) + equal_nums + quick_sort(greater)

Or try to use(and understand) more pythonic solution:

def qsort(L):
    if L: return qsort([x for x in L if x<L[0]]) + [x for x in L if x==L[0]] + qsort([x for x in L if x>L[0]])
    return []

edited Dec 13, 2018 at 12:07

answered Dec 13, 2018 at 11:44

Max

1,9141 gold badge21 silver badges37 bronze badges

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

4 Comments

Trey Yi Over a year ago

Is it ok to always set the pivot value as L[0]? Does that cause lower performance when sorting? I am just curious. Your answer is very helpful though thanks!

Max Over a year ago

@TreyYi it depends on input data. If your input data will be sorted array with reverse order - this is bad.

Max Over a year ago

@TreyYi i made an edit to my answer: replace else with if i == pivot. Now it works correct.

Trey Yi Over a year ago

Thanks a lot! I did use if i < pivot, elif i > pivot, else # else for equal check.

Martin Frodl · Accepted Answer · 2018-12-13 11:43:30Z

0

The problem is that your are always adding pivot to less when populating the list.

When the algorithm hits the point where it needs to sort the list [3, 3, 3, 3], it picks an arbitrary pivot, create a new list less which will again contain all the values (because all the 3's are less than equal to the pivot 3). When it tries to sort this new list which is identical to the original one, it eventually leads to an infinite recursion.

answered Dec 13, 2018 at 11:43

Martin Frodl

6574 silver badges11 bronze badges

Comments

MBo · Accepted Answer · 2018-12-13 12:20:43Z

You should temporarily remove pivot element from list or exchange it with the last element and make loop excluding the last element. Otherwise it takes part in sorting again and again, causing too deep recursion and stackoverflow

Corrected working code:

def quick_sort(arr):
    # if array is empty or has only 1 element
    # it means the array is already sorted, so return it.
    if len(arr) < 2:
        return arr
    else:
        rand_index = random.randint(0,len(arr)-1)
        pivot = arr[rand_index]
        less = []
        greater = []

        arr[-1], arr[rand_index] = arr[rand_index], arr[-1]


        # create less and greater array comparing with pivot
        for i in range(len(arr)-1):
            if arr[i] <= pivot:
                less.append(arr[i])
            else:
                greater.append(arr[i])

        return quick_sort(less) + [pivot] + quick_sort(greater)

>>> [0, 1, 2, 3, 3, 3, 3, 4, 5, 6, 6, 7, 7, 7, 21, 54]

Josep Antoni Costa Camps · Accepted Answer · 2018-12-13 11:49:39Z

-1

Try this:

rand_index = random.randint(0,len(arr)-1)
pivot = arr[rand_index]
less = []
equal = []
greater = []

# create less and greater array comparing with pivot
for i in arr:
    if i < pivot:
        less.append(i)
    elif i == pivot:
        equal.append(i)
    else:
        greater.append(i)

return quick_sort(less) + equal + quick_sort(greater)

edited Dec 13, 2018 at 11:49

answered Dec 13, 2018 at 11:42

Josep Antoni Costa Camps

445 bronze badges

2 Comments

nightgaunt Over a year ago

This will skip values which are equal to pivot from sorting.

user2261062 Over a year ago

using elif and else you can avoid two unnecessary conditional checkings

Collectives™ on Stack Overflow

python quicksort using rescursion

4 Answers 4

4 Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related