which of these 2 quicksorts is faster?

process circularfunc at gmail.com
Wed Sep 10 12:17:30 CEST 2008


qsort can handle bigger lists it seems, making less recursive calls
before finishing(quicksort blows the stack when sorting
range(100,-1000,-1).
qsort does more work though right? is there a way to speed up that?

is the built-in sort not defined recursively?

def quicksort(lista):
    if len(lista) != 0:
        return quicksort([x for x in lista[1:] if x < lista[0]]) +
[lista[0]] + \
               quicksort([x for x in lista[1:] if x >= lista[0]])
    else:
        return []

def qsort(lista):
    l = len(lista)
    if len(lista) != 0:
        return qsort([x for x in lista[:l/2]+lista[l/2+1:] if x <
lista[l/2]]) + \
               [lista[l/2]] + \
               qsort([x for x in lista[:l/2]+lista[l/2+1:] if x >=
lista[l/2]])
    else:
        return []



More information about the Python-list mailing list