Comparing several sorting methods

Hello! I really hope I can get some help understanding this! I want to graph the different running time of each sorting method using pylab, but I don’t understand what I need to add to the code to make it show, or even compare sorting methods given.

any help would be MUCH appreciated!!!

def selectionSort(L):
i = 0
# invariant: L[0:i] sorted and in final position
while i < len(L):
minIndex = findMinIndex(L, i)
L[i], L[minIndex] = L[minIndex], L[i]
# now L[0:i+1] sorted an in final position.
i = i + 1
# L[0:i] sorted/in final position,and “loop invariant” (loop entry point assumption) holds again

    ## uncomment this if you want to see progress (don't do for large L though!)
    #print("sorted and in final pos:", L[0:i], "unsorted:", L[i:])

return index of min item in L[startIndex:]

assumes startIndex < len(L)

def findMinIndex(L, startIndex):
minIndex = startIndex
currIndex = minIndex + 1
while currIndex < len(L):
if L[currIndex] < L[minIndex]:
minIndex = currIndex
currIndex = currIndex + 1
return minIndex

def insertionSort(L):
i = 1

# invariant: L[0:i] is sorted
while i < len(L):
    itemToMove = L[i]
    # find where itemToMove should go, shifting larger items right one slot along the way
    j = i-1
    while ((j>=0) and (itemToMove<L[j])):
        L[j+1] = L[j]
        j = j-1

    # found the spot - put itemToMove there
    L[j+1] = itemToMove

    # now L[0:i+1] is sorted (though items not necessarily in final position)
    i = i + 1
    # L[0:i] sorted and "loop invariant" (loop entry point assumption) holds again

    ## uncomment this if you want to see progress (don't do for large L though!)
    #print("sorted:", L[0:i], "unsorted:", L[i:])
    
return

Recursive version of merge sort.

(It’s much easier for most people to correctly implement mergesort recursively.)

Note: this version modifies L itself, like the other sorts.

def mergeSort(L):
if (len(L) < 2):
return
else:
# 1. divide list into (almost) equal halves
middleIndex = len(L)//2
left = L[:middleIndex]
right = L[middleIndex:]

    #2. recursively sort left and right parts
    mergeSort(left)
    mergeSort(right)
    
    #3. merge sorted left/right parts
    mergedL = merge(left, right)
    
    # mergedL is now sorted but we need to do one more thing (related to Note above)
    # this copies the contents of margedL into L
    L[:] = mergedL[:]
    return

Merge function used by both the recursive and non-recursive merge sorts.

def merge(L1, L2):
mergedL =
iL1 = 0
iL2 = 0

while iL1 != len(L1) and iL2 != len(L2):
    if L1[iL1] <= L2[iL2]:
        mergedL.append(L1[iL1])
        iL1 = iL1 + 1
    else:
        mergedL.append(L2[iL2])
        iL2 = iL2 + 1

# At this point, we've used up all the items from one of the lists.
# Use list "extend" method to add all the remaining items to mergedL
mergedL.extend(L1[iL1:])
mergedL.extend(L2[iL2:])

return mergedL

def builtinSort(L):
L.sort()

##########

import random

return a new list with the same elements as input L but randomly rearranged

def mixup(L):
newL = L[:]
length = len(L)
for i in range(length):
newIndex = random.randint(i,length-1)
newL[newIndex], newL[i] = newL[i], newL[newIndex]
return(newL)

##########

import time

def timeSort(sortfn, L):
t1 = time.time()
sortfn(L)
t2 = time.time()
return (t2 - t1)

try, e.g.,

l = mixup(list(range(4000)))

timeAllSorts(l)

def timeAllSorts(L):

Lcopy = L[:]
sTime = timeSort(selectionSort, Lcopy)
Lcopy = L[:]
iTime = timeSort(insertionSort, Lcopy)
Lcopy = L[:]
mTime = timeSort(mergeSort, Lcopy)
Lcopy = L[:]
biTime = timeSort(builtinSort, Lcopy)

print("{}\t sel: {:.2f}\t ins: {:.2f}\t merge: {:.2f}\t builtin: {:.2f}".format(len(L), sTime, iTime, mTime, biTime))

The code below is commented out (with ‘’’ before and after) so that the code above will run even

when you are using a Python that does not have pylab. If you are using a Python

with pylab, as you will need to for HW P2, remove the ‘’'s.

As demonstrated in Lecture 25, you can call “compareSorts” to produce a chart graphing running times

or selection and insertion sort on randomly ordered lists of various sizes.

For HW 5, consider using several functions like this to compare all the sorting methods on various kinds of da

import pylab
def compareSorts(minN = 1000, maxN=20000, step=2000):
listSizes = list(range(minN, maxN, step))
selectionSortTimes =
insertionSortTimes =
for listSize in listSizes:
listToSortOrig = mixup(list(range(listSize)))
listToSort = listToSortOrig[:]
startTime = time.time()
selectionSort(listToSort)
endTime = time.time()
selectionSortTimes.append(endTime-startTime)
listToSort = listToSortOrig[:]
startTime = time.time()
insertionSort(listToSort)
endTime = time.time()
insertionSortTimes.append(endTime-startTime)
pylab.figure(1)
pylab.clf()
pylab.xlabel(‘List size’)
pylab.ylabel(‘Time (s)’)
pylab.title(“Selection (blue) vs Insertion (red) sort on random data”)
pylab.plot(listSizes, selectionSortTimes, ‘bo-’)
pylab.plot(listSizes, insertionSortTimes, ‘ro-’)