Measuring time of Quick and Heap sort in python

Question

I'm measuring time of Quick and Heap sort in Python, but the diffrence between results is too big. Please take a moment to look at my code:

import time
import linecache
import random

def shell_sort(some_list):
    h=1
    while(h<=len(some_list)):
        h=3*h+1
    while h>0:
        for i in xrange(len(some_list)):
            j = i
            temp = some_list[i]
            while j >= h and some_list[j-h] > temp:
                some_list[j] = some_list[j - h]
                j -= h
            some_list[j] = temp
        h = h/3 if h/9 else (0 if h==1 else 1)
    some_list.reverse()

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

def gen(number, b=100000):
    #return [random.randint(0, b) for x in xrange(number)]
    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()
        shell_sort(temp_list)
        end = time.time() - start
        print end
    print '*************************'

I'm using two types of code in function 'gen'. First works with heap sort and the second with quick sort. Hopefully there is too big difference and this cannot be correct. QS for 1000000 elements is about 0.5 s and HS is 23 s. What's wrong?

Thanks from advance.

Answer 1

This line:

return [some_list.append(random.randint(0, b)) for x in xrange(number)]

... is a list comprehension that generates the result of number calls to some_list.append(...), all of which return None:

>>> print gen(10)
[None, None, None, None, None, None, None, None, None, None]

Nones compare like this:

>>> None < None
False
>>> None > None
False

So I would imagine both of your sorts are rather confused.

The quicksort is faster because with a list of Nones, it becomes a function that copies a list:

def quick_sort_r(some_list):
    e = []
    if len(some_list) <= 1:
        return some_list
    else:
        pivot = some_list[0]
        for x in some_list:
            # all other comparisons are False
            e.append(x)

        return e

In summary, use return [random.randint(0, b) for x in xrange(number)] instead. On my machine, that change takes the quicksort from 0.43s to 8.9s, which is probably more what you were expecting.

Incidentally, unless you have a fast machine, Python isn't going to agree with a list of 1,000,000 numbers very well - it takes my (somewhat slow) computer about 3 seconds to generate a list of 1 million numbers.