In [1]:
# The Sound of Sorting Algorithms in Python's Taste #

# 1
def bubble_sort(seq):
""" worst(n^2), best(n), avg(n^2)
stable: yes
"""
for passnum in range(len(seq) - 1, 0, -1):
for i in range(passnum):
if seq[i] > seq[i + 1]:
seq[i], seq[i + 1] = seq[i + 1], seq[i]

# 2
def selection_sort(seq):
""" worst(n^2), best(n^2), avg(n^2)
stable: no
"""
for i in range(len(seq) - 1):
mini, miniat = seq[i], i
for j in range(i + 1, len(seq)):
if seq[j] < mini: mini, miniat = seq[j], j
seq[i], seq[miniat] = seq[miniat], seq[i]

# 3
def insertion_sort(seq):
""" worst(n^2), best(n), avg(n^2)
stable: yes
"""
for i in range(1, len(seq)):
j = i
while j > 0 and seq[j - 1] > seq[j]:
seq[j - 1], seq[j] = seq[j], seq[j - 1]
j -= 1

# 4
def partition(seq):
pi, seq = seq[0], seq[1:]
lo = [x for x in seq if x <= pi]
hi = [x for x in seq if x > pi]
return lo, pi, hi

def quicksort(seq):
""" worst(n^2), best(n lgn), avg(n lgn)
stable: no
"""
if len(seq) <= 1: return seq
lo, pi, hi = partition(seq)
return quicksort(lo) + [pi] + quicksort(hi)

# 5
def mergesort(seq):
""" worst(n lgn), best(n lgn), avg(n lgn)
stable: yes
"""
mid = len(seq) // 2
lft, rgt = seq[:mid], seq[mid:]
if len(lft) > 1: lft = mergesort(lft)
if len(rgt) > 1: rgt = mergesort(rgt)
res = []
while lft and rgt:
if lft[-1] >= rgt[-1]:
res.append(lft.pop())
else:
res.append(rgt.pop())
res.reverse()
return (lft or rgt) + res

# 6
def heapify(seq, i, n):
l, r = 2 * i + 1, 2 * (i + 1)
maxat = i
if l <= n and seq[l] > seq[i]:
maxat = l
if r <= n and seq[r] > seq[maxat]:
maxat = r
if maxat != i:
seq[i], seq[maxat] = seq[maxat], seq[i]
heapify(seq, maxat, n)

def buildheap(seq, s, n):
for i in range(s, -1, -1):
heapify(seq, i, n)

def heapsort(seq):
""" worst(n lgn), best(n lgn), avg(n lgn)
stable: no
"""
end = len(seq) - 1
start = end / 2
buildheap(seq, start, end)

for i in range(end, 0, -1):
seq[0], seq[i] = seq[i], seq[0]
end -= 1
heapify(seq, 0, end)

# Last updated: Thu May  8 00:53:29 EDT 2014, by: Aziz Altowayan, thnx: Python Algorithms (Hetland) and Wikipedia.

In [2]:
# Test (time complexity)
from random import randrange
import time

def test(algorithms):

global analysisdict

for algo in algorithms:
algoname = algo.__name__
size, period = [], []
for lstlngth in range(100, 1001, 100):
lst = [randrange(1000) for _ in range(lstlngth)]
start = time.time()
algo(lst)
end = time.time()
size.append(lstlngth)
period.append(end - start)

analysisdict[algoname] = zip(size, period)

if __name__ == '__main__':
toTest = [selection_sort, bubble_sort, mergesort, insertion_sort, quicksort, heapsort]
analysisdict = {}
test(toTest)

# print results
d = analysisdict
for k, v in d.items():
print k
print("size\ttime")
for e in v:
size, time = e
print size, time

# plot results
import matplotlib
import matplotlib.pyplot as plt
from math import log

for k, v in d.items():
plt.plot(*zip(*v), label=k)

plt.title('comparison-sort algorithms compared')
plt.xlabel('Size of the list')
plt.ylabel('Time taken to sort the list (sec)')
plt.legend(loc='upper left')
matplotlib.rcParams['savefig.dpi'] =  2 * matplotlib.rcParams['savefig.dpi'] # frame size
plt.show()

mergesort
size	time
100 0.00633192062378
200 0.00149202346802
300 0.00209498405457
400 0.00292110443115
500 0.00370216369629
600 0.00476312637329
700 0.00541806221008
800 0.00639700889587
900 0.00874900817871
1000 0.00988793373108
bubble_sort
size	time
100 0.00157690048218
200 0.0156350135803
300 0.0210530757904
400 0.0282511711121
500 0.041209936142
600 0.0833599567413
700 0.141782045364
800 0.21363401413
900 0.175294876099
1000 0.185271978378
heapsort
size	time
100 0.001060962677
200 0.00188016891479
300 0.00243592262268
400 0.00350284576416
500 0.00563597679138
600 0.00622510910034
700 0.00658798217773
800 0.00821995735168
900 0.0100078582764
1000 0.00982403755188
quicksort
size	time
100 0.000342845916748
200 0.000761032104492
300 0.00166583061218
400 0.00194597244263
500 0.00236892700195
600 0.00248193740845
700 0.00281310081482
800 0.00371909141541
900 0.00354909896851
1000 0.00511002540588
selection_sort
size	time
100 0.000715970993042
200 0.00251412391663
300 0.00557804107666
400 0.00988411903381
500 0.0125319957733
600 0.0192949771881
700 0.0313279628754
800 0.0311489105225
900 0.0593688488007
1000 0.0747320652008
insertion_sort
size	time
100 0.00135779380798
200 0.00532793998718
300 0.0128440856934
400 0.0212721824646
500 0.0358898639679
600 0.0465190410614
700 0.0692429542542
800 0.0852708816528
900 0.114698886871
1000 0.147146940231


In [7]:
# Test (time complexity)
from random import randrange
import time

def testit(algorithms):

global analysisdict

for algo in algorithms:
algoname = algo.__name__
size, period = [], []
for lstlngth in range(1000, 10001, 1000):
lst = [randrange(1000) for _ in range(lstlngth)]
start = time.time()
algo(lst)
end = time.time()
size.append(lstlngth)
period.append(end - start)

analysisdict[algoname] = zip(size, period)

In [8]:
""" Quadratic algorithms """
if __name__ == '__main__':
toTest = [selection_sort, bubble_sort, insertion_sort]
analysisdict = {}
testit(toTest)

# plot results
d = analysisdict
for k, v in d.items():
plt.plot(*zip(*v), label=k)

plt.xlabel('Size of the list')
plt.ylabel('Time taken to sort the list (sec)')
plt.legend(loc='upper left')
plt.show()

In [9]:
""" Loglinear algorithms """
if __name__ == '__main__':
toTest = [mergesort, heapsort, quicksort]
analysisdict = {}
testit(toTest)

# plot results
d = analysisdict
for k, v in d.items():
plt.plot(*zip(*v), label=k)

plt.title('Algorithms with Loglinear running time')
plt.xlabel('Size of the list')
plt.ylabel('Time taken to sort the list (sec)')
plt.legend(loc='upper left')
plt.show()

In [10]:
# Test (time complexity)
""" Reversed List """

def test_reverse(algorithms):

global analysisdict

for algo in algorithms:
algoname = algo.__name__
size, period = [], []
for lstlngth in range(10, 901, 100):
lst = [x for x in range(lstlngth, 0, -1)]
start = time.time()
algo(lst)
end = time.time()
size.append(lstlngth)
period.append(end - start)
analysisdict[algoname] = zip(size, period)

In [11]:
""" Quadratic algorithms with reversed list """
if __name__ == '__main__':
toTest = [selection_sort, bubble_sort, insertion_sort]
analysisdict = {}
test_reverse(toTest)

# plot results
d = analysisdict
for k, v in d.items():
plt.plot(*zip(*v), label=k)

plt.xlabel('Size of the list')
plt.ylabel('Time taken to sort the list (sec)')
plt.legend(loc='upper left')
plt.show()

In [12]:
""" Loglinear algorithms with reversed list """
if __name__ == '__main__':
toTest = [mergesort, heapsort, quicksort]
analysisdict = {}
test_reverse(toTest)

# plot results
d = analysisdict
for k, v in d.items():
plt.plot(*zip(*v), label=k)

plt.title('Loglinear algorithms with reversed list')
plt.xlabel('Size of the list')
plt.ylabel('Time taken to sort the list (sec)')
plt.legend(loc='upper left')
plt.show()

By: Aziz Altowayan, Thu May 15 15:32:40 EDT 2014