Sorting Code Examples and Timing
# sorting.py
import time, random, sys
####################################################
# swap
####################################################
def swap(L, i, j):
L[i], L[j] = L[j], L[i]
####################################################
# selectionSort
####################################################
def selectionSort(L):
n = len(L)
for startIndex in range(n):
minIndex = startIndex
for i in range(startIndex+1, n):
if L[i] < L[minIndex]:
minIndex = i
swap(L, startIndex, minIndex)
####################################################
# mergeSort
####################################################
def merge(L, start1, start2, end):
index1 = start1
index2 = start2
length = end - start1
aux = [None] * length
for i in range(length):
if ((index1 == start2) or
((index2 != end) and (L[index1] > L[index2]))):
aux[i] = L[index2]
index2 += 1
else:
aux[i] = L[index1]
index1 += 1
for i in range(start1, end):
L[i] = aux[i - start1]
def mergeSort(L):
n = len(L)
step = 1
while (step < n):
for start1 in range(0, n, 2*step):
start2 = min(start1 + step, n)
end = min(start1 + 2*step, n)
merge(L, start1, start2, end)
step *= 2
####################################################
# builtinSort (wrapped as a function)
####################################################
def builtinSort(L):
L.sort()
####################################################
# testSort
####################################################
def testSort(sortFn, n):
L = [random.randint(0,2**31) for i in range(n)]
sortedL = sorted(L)
startTime = time.time()
sortFn(L)
endTime = time.time()
elapsedTime = endTime - startTime
assert(L == sortedL)
print(f'{sortFn.__name__:>20} n={n}, time={elapsedTime:6.3f}')
def testSorts():
if sys.platform == 'brython':
sizes = [2**9, 2**10]
else:
sizes = [2**12, 2**13, 2**14]
for n in sizes:
print(f'Testing sorts for n = {n}:')
for sortFn in [selectionSort, mergeSort, builtinSort]:
testSort(sortFn, n)
testSorts()