Quick sort and setting the limit of recursion

Question

I have my quick sort algorithm in recursion version:

def quick_sort_r(some_list):
    less = []
    equal = []
    greater = []
    if len(some_list) <= 1:
        return some_list
    else:
        pivot = some_list[0]
        for x in some_list:
            if x < pivot:
                less.append(x)
            elif x > pivot:
                greater.append(x)
            else:
                equal.append(x)
        less = quick_sort_r(less)
        greater = quick_sort_r(greater)
        return greater + equal + less

def gen(number, some_list, b=100000):
    "Generating list of random numbers".
    for x in range(number):
        x = n.random.randint(b, size=1)
        some_list.extend(x)
        x=x-1

domain = [10000, 25000, 50000, 100000, 200000, 300000, 400000, 500000, 750000, 1000000]
for i in range(len(domain)):
    print 'Results for: ' + str(domain[i]) + ' elements:'
    for j in range(0,10):
        list=[]
        gen(dziedzina[i], list)
        start = time.time()
        quick_sort_r(list)
        end = time.time() - start
        print end
    print '*************************'

Yes it should be in recursion version and yes it should be descending sort.

Of course I have this classic error:

maximum recursion depth exceeded in cmp

Is there any possible limit to generate this results for this domain? I know about:

sys.setrecursionlimit(x)

Answer 1

There were a few mistakes with your code which might have lead to the recursion issues.

1. You were overriding the built-in datatype 'list'.
2. Your gen method was actually trying to create list of lists, instead of creating list of random numbers.

A few suggestion too:

1. You should be reading into list comprehensions. :)
2. You could use the timeit module for checking the time taken to complete your method execution.

The below code works as expected, if this is what you wanted to do.

import random
import time


def quick_sort_r(some_list):
    less = []
    equal = []
    greater = []
    # print some_list
    if len(some_list) <= 1:
        return some_list
    else:
        pivot = some_list[0]
        for x in some_list:
            if x < pivot:
                less.append(x)
            elif x > pivot:
                greater.append(x)
            else:
                equal.append(x)
        less = quick_sort_r(less)
        greater = quick_sort_r(greater)
        return greater + equal + less


def gen(number, b=100000):
    "Generating list of random numbers"
    some_list = []
    return [some_list.append(random.randint(0, b)) for x in xrange(number)]

domain = [10000, 25000, 50000, 100000, 200000, 300000, 400000, 500000, 750000, 1000000]
for element in domain:
    print 'Results for: ' + str(element) + ' elements:'
    for j in range(0, 10):
        temp_list = gen(element)
        start = time.time()
        quick_sort_r(temp_list)
        end = time.time() - start
        print end
    print '*************************'