In [14]:
def qsort(q):
lesser=[]
greater=[]
if len(q) <= 1:
return q
for i in q[1:]:
if i < q[0]:
lesser.append(i)
else:
greater.append(i)
return qsort(lesser) + q[0:1] + qsort(greater)
In [3]:
import random
from datetime import datetime
In [5]:
def partition_iterative(list, equal):
lesser = []
greater = []
while list != []:
head = list.pop(0)
if head < equal[0]:
lesser.append(head)
elif head > equal[0]:
greater.append(head)
else:
equal.append(head)
print("Equal: ", equal)
return (lesser, equal, greater)
In [6]:
def partition_recursive(list, lesser, equal, greater):
if list == []:
return (lesser, equal, greater)
else:
head = list[0]
if head < equal[0]:
return partition_recursive(list[1:], lesser + [head], equal, greater)
elif head > equal[0]:
return partition_recursive(list[1:], lesser, equal, greater + [head])
else:
return partition_recursive(list[1:], lesser, equal + [head], greater)
In [7]:
def quicksort(list, info):
'''
Quicksort (implementation with partitioning function)
'''
print (info)
if list == []:
print ("Return empty list")
return []
else:
pivot = list[0] # Pick actual element and sort values
#print ("Actual pivot: ", pivot)
lesser, equal, greater = partition_iterative(list[1:], [pivot])
#lesser, equal, greater = partition_recursive(list[1:], [], [pivot], [])
#print ("Actual lesser: ", lesser)
#print ("Actual equal: ",equal)
#print ("Actual greater: ", greater)
print ("Actual return: ", lesser, equal, greater)
return quicksort(lesser, "lesser") + equal + quicksort(greater, "greater")
In [16]:
import random
from datetime import datetime
random.seed(6)
elements = 10
list = random.sample(range(100), elements)
print(list)
start = 0
end = len(list)
print("Computing list with ", len(list), " elements.")
start_time = datetime.now()
print("Start time: " + str(start_time))
#sort = quicksort(list, "start")
sort = qsort(list)
print(sort)
end_time = datetime.now()
print("End time: " + str(end_time))
print("Computing time: " + str(end_time - start_time))