DS&A

Iterative Sorting

Before writing an algorithm, it’s always worth thinking about how you would solve the same problem “by hand”. After all, you can’t write instructions for how to do something if you don’t know how to do it yourself.

The problem we’re currently interested in is sorting — given a list, put its values in order. There are hundreds of algorithms which solve this problem, but ultimately every sorting algorithm does one of two things:

• Put the correct value in each position.
• Put each value in the correct position.

Of course, both achieve the same result (a sorted list) in different ways. In this post we’ll consider two of the simplest sorting algorithms — selection sort and insertion sort — which are direct implementations of these two ideas. For both algorithms we’ll present two versions: one “in-place” and one “out-of-place”.

Selection sort

The basic idea of the selection sort algorithm is “for each position, find the correct value and put it there”. Here’s how it works:

• The correct value for index 0 is whichever is smallest.
• The correct value for index 1 is the next-smallest after that.
• The correct value for index 2 is the next-smallest after that.
• The correct value for index 3 is the next-smallest after that.
• …and so on.

Try sorting a list with the model below:

This model shows an “out-of-place” sort, because there are separate lists for the input and the result.(1)

When we select a value from the input list, we have to remove it to make sure we won’t select it again. In a real implementation, we would need to copy the input list, so that we can remove values from the copy without destroying the original.

The proper selection sort algorithm is the “in-place” version — rather than using a separate list, we will swap the correct values into place. Try it out below:

Because this algorithm swaps values into place from left-to-right, the list has a “sorted” part and an “unsorted” part; when selecting the next-smallest value, we must choose from the “unsorted” part. Finding the index of the correct value is a subproblem.

The code below implements the selection sort algorithm in Python:

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        # find the index of the smallest remaining value
        min_index = i
        for j in range(i+1, n):
            if lst[j] < lst[min_index]:
                min_index = j
        
        # swap the smallest value into place
        tmp = lst[i]
        lst[i] = lst[min_index]
        lst[min_index] = tmp

Insertion sort

The basic idea of the insertion sort algorithm is “for each value, find the correct position and insert it there”. Here’s how it works:

• The first value goes at index 0.
• The next value goes at index 0 or 1, depending on the value.
• The next value goes at index 0, 1 or 2, depending on the value.
• The next value goes at index 0, 1, 2 or 3, depending on the value.
• …and so on.

Try sorting a list with the model below:

This is an “out-of-place” sort; however, this time we don’t have to remove values from the input list when we use them.

The proper insertion sort algorithm is the “in-place” version. Again, to sort in-place, the list will have a “sorted” part and an “unsorted” part. Try it out below:

When inserting, we take the next value from the “unsorted” part and insert it at the correct index in the “sorted” part. However, rather than remove the value and then re-insert it, it’s more efficient to swap it to the left, one index at a time.

The code below implements the insertion sort algorithm in Python:

def insertion_sort(lst):
    n = len(lst)
    for i in range(n):
        j = i
        while j > 0 and lst[j-1] > lst[j]:
            # swap the current value one space left
            tmp = lst[j]
            lst[j] = lst[j-1]
            lst[j-1] = tmp
            j -= 1

Footnotes

1. Technically, any algorithm which uses a second list is “out-of-place”, even if the final result ends up in the original list.

• Tags: 
• sorting, lists, algorithms