Exercises for Lesson 26

Back to Lesson 26

Exercise: Running time of selection sort

Here is the Python code for selection sort:

def getMinIndex(mylist, start):
    # Find the minimum element of those from startIdx
    # to the end of the list
    minIdx = start
    for i in range(start+1, len(mylist)):
        # Is this one smaller?
        if mylist[i] < mylist[minIdx]:
            # If so, update the index we're tracking
            minIdx = i
    return minIdx

def selectionSort(mylist):
    n = len(mylist)

    # Consider each starting index except the last, as that
    # will be the maximum element in the list by the time
    # we finish with the second-to-last position
    for startIdx in range(n-1):
        minIdx = getMinIndex(mylist, startIdx)

        # Swap to put the minimum element (of those startIdx->end)
        # in position startIdx
        mylist[startIdx], mylist[minIdx] = mylist[minIdx], mylist[startIdx]

Part a: Predicting running times

Recall that we said that selection sort makes a number of comparisons (the if condition check in the code above) equal to n(n-1)/2. Using that information, fill in the following table.

n # comparisons
2
4
8
16
32
64
128
256

Part b: Plotting running times

The expression in part (a) is roughly equal to n**2 as n gets really big. Download this selection sort program and run it to graph how long it takes to sort a random list, on average.

Note that with 1000 data points per value of n and with the given list of values of n, it might take at least five minutes to run. You can decrease numTests to make it run faster, although then it won’t test with as much data.

Back to Lesson 26