Skip to content

Instantly share code, notes, and snippets.

@Plutor
Created August 31, 2012 13:00
Show Gist options
  • Save Plutor/3552380 to your computer and use it in GitHub Desktop.
Save Plutor/3552380 to your computer and use it in GitHub Desktop.
A bunch of sort algorithms
from random import shuffle
import time
def generate_array(size):
result = [i for i in range(0, size)]
shuffle(result)
return result
def is_in_order(a, size):
if (len(a) != size):
return False
for n in range(0, size):
if (n != a[n]):
return False
return True
iters=5
def test_sort(f, size=10):
totalt = 0
for n in range(0, iters):
a = generate_array(size)
t1 = time.time()
a = f(a) # Run
t2 = time.time()
totalt += (t2-t1)
dur = "%.1f ms" % (totalt*1000/iters)
if (is_in_order(a, size)):
print("%s ok (%s)" % (f.__name__, dur))
else:
print("%s ERROR (%s)" % (f.__name__, dur))
# ==========================================================
def null_sort(a):
return a
# ==========================================================
def insertion_sort(a):
# 0 is already sorted
# for each element
for n in range(1, len(a)):
item = a[n]
# walk backwards, shifting elements to the right
# until you find one less than it
for m in range(n, 0, -1):
if (item < a[m-1]):
a[m] = a[m-1]
else:
break
else:
m = 0
# place the item there
a[m] = item
return a
# ==========================================================
def merge_sort(a):
if (len(a) <= 1):
return a
mid = int(len(a)/2)
left = [a[i] for i in range(0,mid)]
left = merge_sort(left)
right = [a[i] for i in range(mid,len(a))]
right = merge_sort(right)
# now merge left and right
n = 0
m = 0
while (True):
if (n < len(left) and m < len(right)):
if (left[n] < right[m]):
a[n+m] = left[n]
n += 1
else:
a[n+m] = right[m]
m += 1
elif (n < len(left)):
a[n+m] = left[n]
n += 1
elif (m < len(right)):
a[n+m] = right[m]
m += 1
else:
break
return a
# ==========================================================
def heap_sort(a):
def sift_down(start, end):
while start*2+1 <= end:
swap = start
if a[swap] < a[start*2+1]:
swap = start*2+1 # left child is greater
if start*2+2 <= end and a[swap] < a[start*2+2]:
swap = start*2+2 # right child exists and is greater
if swap != start: # if either is greater, swap
temp = a[start]
a[start] = a[swap]
a[swap] = temp
start = swap # and keep going downward
else:
return
# heapify
lastparent = int((len(a)-2)/2)
for n in range(lastparent, -1, -1):
sift_down(n, len(a)-1)
for n in range(len(a)-1, -1, -1):
# swap the first and last and re-heapify
temp = a[0]
a[0] = a[n]
a[n] = temp
sift_down(0, n-1)
return a
# ==========================================================
def quick_sort(a):
if (len(a) <= 1):
return a
# The pivot is the median of the first, middle, and last vals
# Put the pivot in the 0 spot
mid = int(len(a)/2)
if ((a[0] < a[mid]) != (a[0] < a[-1])):
pass
elif ((a[0] < a[mid]) == (a[mid] < a[-1])):
swap = a[0]
a[0] = a[mid]
a[mid] = swap
else:
swap = a[0]
a[0] = a[-1]
a[-1] = swap
# Segment in half
left = [i for i in a[1:] if i < a[0]]
left = quick_sort(left)
right = [i for i in a[1:] if i >= a[0]]
right = quick_sort(right)
return left + [a[0]] + right
# ==========================================================
for size in [16, 64, 10240]:
print("\nn = %d" % size)
test_sort(null_sort, size)
test_sort(insertion_sort, size)
test_sort(merge_sort, size)
test_sort(heap_sort, size)
test_sort(quick_sort, size)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment