Insertion Sort Using Python

I mentioned on twitter that I wrote a quick insertion sort function in Python using Pythonista on my iPad Pro. Searching and sorting algorithms are very popular subjects in my computer since and algorithms classes, so I am familiarizing myself with the more common ones and coding them up using Python and C#. I've already mentioned a couple of popular sorting algorithms in articles: selection sort and merge sort.

Insertion Sort

Insertion Sort is O(n²) and iterates through each item in the list, inserting each one in its proper location within the sorted items. Here is one solution to insertion sort in Python.

def insertion_sort(integers):
    """Sorts a list of integers in-place.
    
    :param list integers: List of integers to sort.
    :return: Nothing. Sorts in-place.
    :rtype: None
    
    >>> lst = []
    >>> insertion_sort(lst)
    >>> assert(lst == [])
    >>> lst = [1]
    >>> insertion_sort(lst)
    >>> assert(lst == [1])
    >>> lst = [1, 2]
    >>> insertion_sort(lst)
    >>> assert(lst == [1, 2])
    >>> lst = [2, 1]
    >>> insertion_sort(lst)
    >>> assert(lst == [1, 2])
    >>> lst = [5, 4, 3, 2, 1, 0]
    >>> insertion_sort(lst)
    >>> assert(lst == [0, 1, 2, 3, 4, 5])
    >>> lst = [100, 84, 100, 16, 34, 34, 19, 0, 6, 100]
    >>> insertion_sort(lst)
    >>> assert(lst == [0, 6, 16, 19, 34, 34, 84, 100, 100, 100])
    """
    if len(integers) < 2:
        return
    
    for i in range(1, len(integers)):
        value = integers[i]
        j = i
        while j > -1:
            j -= 1
            if value > integers[j]:
                break
            integers[j+1] = integers[j]
            
        integers[j+1] = value

The code for insertion sort is short. I just included several Doctests for the function.

If you are learning various computer science topics and algorithms, I hope you find the code useful!

I hope to see on you twitter. I am @KoderDojo

Related Posts: