394 lines
11 KiB
Plaintext
394 lines
11 KiB
Plaintext
import random
|
|
import time
|
|
import copy
|
|
size1 = 100
|
|
size2 = 10000
|
|
size3 = 1000000
|
|
span = 1000000
|
|
threshold = 20
|
|
|
|
#---------------------------------------
|
|
# Insertion Sort
|
|
#---------------------------------------
|
|
# not optimized, equiv to while version below, but uses for loop
|
|
def insertion_sort1(A):
|
|
for i in range(1, len(A)):
|
|
for j in range(i-1, -1, -1):
|
|
if A[j] > A[j+1]:
|
|
A[j], A[j+1] = A[j+1], A[j]
|
|
else:
|
|
break
|
|
|
|
# not optimized, equiv to break version, but uses while loop
|
|
def insertion_sort2(A):
|
|
for i in range(1, len(A)):
|
|
j = i-1
|
|
while A[j] > A[j+1] and j >= 0:
|
|
A[j], A[j+1] = A[j+1], A[j]
|
|
j -= 1
|
|
|
|
# optimized - shifts instead of swapping
|
|
def insertion_sort3(A):
|
|
for i in range(1, len(A)):
|
|
curNum = A[i]
|
|
k = 0
|
|
for j in range(i-1, -2, -1):
|
|
k = j
|
|
if A[j] > curNum:
|
|
A[j+1] = A[j]
|
|
else:
|
|
break
|
|
A[k+1] = curNum
|
|
|
|
#---------------------------------------
|
|
# Selection Sort
|
|
#---------------------------------------
|
|
def selection_sort(A):
|
|
for i in range (0, len(A) - 1):
|
|
minIndex = i
|
|
for j in range (i+1, len(A)):
|
|
if A[j] < A[minIndex]:
|
|
minIndex = j
|
|
if minIndex != i:
|
|
A[i], A[minIndex] = A[minIndex], A[i]
|
|
|
|
#---------------------------------------
|
|
# Bubble Sort
|
|
#---------------------------------------
|
|
# not optimized
|
|
def bubble_sort1(A):
|
|
for i in range (0, len(A) - 1):
|
|
for j in range (0, len(A) - i - 1):
|
|
if A[j] > A[j+1]:
|
|
A[j], A[j+1] = A[j+1], A[j]
|
|
|
|
# optimized to exit if no swaps occur
|
|
def bubble_sort2(A):
|
|
for i in range (0, len(A) - 1):
|
|
done = True
|
|
for j in range (0, len(A) - i - 1):
|
|
if A[j] > A[j+1]:
|
|
A[j], A[j+1] = A[j+1], A[j]
|
|
done = False
|
|
if done:
|
|
return
|
|
|
|
#---------------------------------------
|
|
# Merge Sort
|
|
#---------------------------------------
|
|
def merge_sort(A):
|
|
merge_sort2(A, 0, len(A)-1)
|
|
|
|
def merge_sort2(A, first, last):
|
|
if last-first < threshold and first < last:
|
|
quick_selection(A, first, last)
|
|
elif first < last:
|
|
middle = (first + last)//2
|
|
merge_sort2(A, first, middle)
|
|
merge_sort2(A, middle+1, last)
|
|
merge(A, first, middle, last)
|
|
|
|
def merge(A, first, middle, last):
|
|
L = A[first:middle]
|
|
R = A[middle:last+1]
|
|
L.append(999999999)
|
|
R.append(999999999)
|
|
i = j = 0
|
|
|
|
for k in range (first, last+1):
|
|
if L[i] <= R[j]:
|
|
A[k] = L[i]
|
|
i += 1
|
|
else:
|
|
A[k] = R[j]
|
|
j += 1
|
|
#---------------------------------------
|
|
# Quick Sort
|
|
#---------------------------------------
|
|
def quick_sort(A):
|
|
quick_sort2(A, 0, len(A)-1)
|
|
|
|
def quick_sort2(A, low, hi):
|
|
if hi-low < threshold and low < hi:
|
|
quick_selection(A, low, hi)
|
|
elif low < hi:
|
|
p = partition(A, low, hi)
|
|
quick_sort2(A, low, p - 1)
|
|
quick_sort2(A, p + 1, hi)
|
|
|
|
def get_pivot(A, low, hi):
|
|
mid = (hi + low) // 2
|
|
s = sorted([A[low], A[mid], A[hi]])
|
|
if s[1] == A[low]:
|
|
return low
|
|
elif s[1] == A[mid]:
|
|
return mid
|
|
return hi
|
|
|
|
def partition(A, low, hi):
|
|
pivotIndex = get_pivot(A, low, hi)
|
|
pivotValue = A[pivotIndex]
|
|
A[pivotIndex], A[low] = A[low], A[pivotIndex]
|
|
border = low
|
|
|
|
for i in range(low, hi+1):
|
|
if A[i] < pivotValue:
|
|
border += 1
|
|
A[i], A[border] = A[border], A[i]
|
|
A[low], A[border] = A[border], A[low]
|
|
|
|
return (border)
|
|
|
|
def quick_selection(x, first, last):
|
|
for i in range (first, last):
|
|
minIndex = i
|
|
for j in range (i+1, last+1):
|
|
if x[j] < x[minIndex]:
|
|
minIndex = j
|
|
if minIndex != i:
|
|
x[i], x[minIndex] = x[minIndex], x[i]
|
|
|
|
#--------------RANDOM ORDER----------------------
|
|
#------------------------------------------------
|
|
# size = 100
|
|
#------------------------------------------------
|
|
print("\nRandom Order\n---------------------------------")
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
insertion_sort3(w)
|
|
print("Insertion Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
selection_sort(w)
|
|
print("Selection Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
bubble_sort2(w)
|
|
print("Bubble Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size1)]
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size1),"): ", (time.clock()-t1) * 1000)
|
|
#------------------------------------------------
|
|
# size = 10,000
|
|
#------------------------------------------------
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
insertion_sort3(w)
|
|
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
selection_sort(w)
|
|
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
bubble_sort2(w)
|
|
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
#------------------------------------------------
|
|
# size = 1,000,000
|
|
#------------------------------------------------
|
|
w = [random.randint(0, span) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, span) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
# ----------------ALREADY SORTED-----------------
|
|
#------------------------------------------------
|
|
# size = 10,000
|
|
#------------------------------------------------
|
|
print("\nAlready Sorted\n---------------------------------")
|
|
|
|
w = [a for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
insertion_sort3(w)
|
|
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
selection_sort(w)
|
|
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
bubble_sort2(w)
|
|
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
#------------------------------------------------
|
|
# size = 1,000,000
|
|
#------------------------------------------------
|
|
w = [a for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
# ----------------REVERSE SORTED-----------------
|
|
#------------------------------------------------
|
|
# size = 10,000
|
|
#------------------------------------------------
|
|
print("\nReverse Sorted\n---------------------------------")
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
insertion_sort3(w)
|
|
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
selection_sort(w)
|
|
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
bubble_sort2(w)
|
|
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size2)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
#------------------------------------------------
|
|
# size = 1,000,000
|
|
#------------------------------------------------
|
|
w = [a for a in range(0, size3)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size3)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [a for a in range(0, size3)]
|
|
w.reverse()
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
#--------------RANDOM ORDER, MANY DUPLICATES------------------
|
|
#------------------------------------------------
|
|
# size = 10,000
|
|
#------------------------------------------------
|
|
print("\nRandom Order, Many Duplicates\n---------------------------------")
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
insertion_sort3(w)
|
|
print("Insertion Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
selection_sort(w)
|
|
print("Selection Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0,size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
bubble_sort2(w)
|
|
print("Bubble Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
quick_sort(w)
|
|
print("Quick Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size2)]
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size2),"): ", (time.clock()-t1) * 1000)
|
|
#------------------------------------------------
|
|
# size = 1,000,000
|
|
#------------------------------------------------
|
|
w = [random.randint(0, size2//10) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
merge_sort(w)
|
|
print("Merge Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
#quick_sort(w)
|
|
#print("Quick Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000)
|
|
|
|
w = [random.randint(0, size2//10) for a in range(0, size3)]
|
|
t1 = time.clock()
|
|
w.sort()
|
|
print("Tim Sort(size=", str(size3),"): ", (time.clock()-t1) * 1000) |