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):
    """
    Finds the position of the minimum element in mylist,
    starting at position start.

    Returns: position (>= start) of minimum element
    """
    # 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):
    """
    Sorts the provided list using the Selection Sort algorithm.

    Returns: None (sorts in place)
    """
    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 num_trials=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 num_trials to make it run faster, although then it won’t test with as much data.

Back to Lesson 26