Skip to content

Instantly share code, notes, and snippets.

@swairshah
Created August 24, 2012 10:30
Show Gist options
  • Save swairshah/3448918 to your computer and use it in GitHub Desktop.
Save swairshah/3448918 to your computer and use it in GitHub Desktop.
Python quicksort comparision
from random import randint
import timeit
import sys
def qsort2(list):
if list == []:
return []
else:
pivot = list[0]
lesser, equal, greater = partition(list[1:], [], [pivot], [])
return qsort2(lesser) + equal + qsort2(greater)
def partition(list, l, e, g):
if list == []:
return (l, e, g)
else:
head = list[0]
if head < e[0]:
return partition(list[1:], l + [head], e, g)
elif head > e[0]:
return partition(list[1:], l, e, g + [head])
else:
return partition(list[1:], l, e + [head], g)
def qsort(list):
if list == []:
return []
pivot = list[0]
l = qsort([x for x in list[1:] if x < pivot])
u = qsort([x for x in list[1:] if x >= pivot])
return l + [pivot] + u
def get_array(n):
l = []
for i in range(n):
l.append(randint(0,n))
return l
def test(n,i):
x=get_array(n)
if i is 1:
qsort(x)
else:
qsort2(x)
if __name__=="__main__":
sys.setrecursionlimit(10000)
print "list-compr 1000 elems",timeit.Timer("test(1000,1)",setup="""from __main__ import test""").timeit(100)
print "recursion 1000 elems",timeit.Timer("test(1000,2)",setup="""from __main__ import test""").timeit(100)
print "list-compr 2000 elems",timeit.Timer("test(2000,1)",setup="""from __main__ import test""").timeit(100)
print "recursion 2000 elems",timeit.Timer("test(2000,2)",setup="""from __main__ import test""").timeit(100)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment