In the introduction to this course (a long time ago) I gave an example whereby you have to sort four cards in ascending order. I asked you to write out, in English, a series of steps which produce, at the end, a sorted pile of cards. The simplest procedure would process the pile multiple times, each time seeking the highest card (or the lowest, depending on the direction in which you want to sort), and putting it aside. This method of sorting, which is called “selection sort”, works as follows:

def selection_sort( tlist ):
    newlist = []
    while len( tlist ) > 0:
        num = min( tlist )
        newlist.append( num )
        tlist.remove( num )
    return newlist
        
numlist = [8, 3, 5, 11, 5, 33, 2, 2, 0, 9, 12, 26, 1, 9, 18]
numlist = selection_sort( numlist )
print( numlist )

Exercise: What is the time complexity of selection_sort() in big-O notation?

Answer: n is the number of items in the list. selection_sort() contains a loop. Each time through the loop, one element is removed, until the list is empty. Therefore, the loop is cycled through n times. Each time through the loop, there will be a selection of the minimum value, an append, and a remove.

• Selection of the minimum means that in the best implementation each item is checked once. So we can say that this is n steps. Naturally, every time through the loop the number of items to check is reduced by 1, so that actually, on average, selecting the minimum needs 0.5*n steps, but for time complexity estimation multiplication with a constant can be ignored.
• Appending an item to the end of a list needs 1 step.
• Removing an item from a list is about as complex as inserting an item into a list; instead of moving a whole bunch of items up, it means moving a whole bunch of items down. In the worst case, the first item from the list is removed, so we can say that this takes n steps (again, on average 0.5*n steps, but we can ignore the constant).

Therefore, selection_sort() needs about n * (n + 1 + n) steps in the worst case, i.e., it is O(n²) (it is also Θ(n²)). This is pretty bad for any sorting algorithm.

The in-place version of selection sort is as follows:

# returns the index of the minimum number in a list, starting at index start
def index_of_minimum( tlist, start ):
    low = start
    for i in range( start+1, len( tlist ) ):
        if tlist[i] < tlist[low]:
            low = i
    return low

def in_place_selection_sort( tlist ):
    for i in range( len( tlist ) ):
        low = index_of_minimum( tlist, i ) # find the index of the lowest at or after index i
        tlist[i], tlist[low] = tlist[low], tlist[i] # swap the items
            
numlist = [8, 3, 5, 11, 5, 33, 2, 2, 0, 9, 12, 26, 1, 9, 18]
in_place_selection_sort( numlist )
print( numlist )

You can check that this implementation of the selection sort method is also O(n²). However, in absolute terms it is a bit faster than the previous implementation (it needs about half the steps), and it has, of course, the advantage that it only needs the original list.

Note that I implemented index_of_minimum() as a separate function. I could have replaced this with a call to tlist.index( min( tlist ) ), but that call has as disadvantage that it first moves through the list to find the minimum, and then moves through the list once more to find the index of the minimum. This call, while making the code quite a bit shorter, would also make it run at half speed. While in general I do not care about that, at this point in your programming career it is good to become aware of such features of an algorithm.