Insertion Sort in Python

Question

This is what I wrote for insertion sort in python. But somehow I'm feeling that it's between bubble and insertion sort.

def insertionSort(lst):
    for i in range(1, len(lst)):
        if lst[i] < lst[i-1]:
            for j in range(i):
                if lst[i] < lst[j]:
                    lst[i], lst[j] = lst[j], lst[i]
    return lst

if __name__ == '__main__':
    lst = [64, 88, 51, 65, 90, 75, 34, 79, 46, 36]
    print insertionSort(lst)

Answer 1

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

_{(source: interactivepython.org)}

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

_{(source: interactivepython.org)}

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)

Answer 2

insertionSort should in Python be insertion_sort [1]. Also, there is not much point in returning the input array.

What comes to your implementation, the line if lst[i] < lst[i-1]: does not buy you anything; remove it.

Finally, there is a variant called straight insertion sort that minimizes the number of assignments by the factor of 3:

def straight_insertion_sort(lst):
    for i in range(1, len(lst)):
        save = lst[i]
        j = i
        while j > 0 and lst[j - 1] > save:
            lst[j] = lst[j - 1]
            j -= 1
        lst[j] = save

You can find the demonstration [2]. It looks like this:

insertionSort in 2941 ms.
straight_insertion_sort in 1977 ms.
Algorithms agree: True

References

[1] PEP 8
[2] Demo program