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(n2) 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

Posted by Koder Dojo

Hi! I am a C# ASP.NET MVC Developer learning Python and ASP.NET Core in the open. This website is full of code examples, and I hope they help you in your adventures and learning. If you want to talk about my examples or are learning yourself, please let me know on twitter (@KoderDojo). I'd love to meet others learning similar topics. Many of the Python articles are based on exercises and problem sets in my computer science, algorithms, data structures, and cryptography courses. The ASP.NET Core samples are mostly just for fun as I learn to understand ASP.NET Core from scratch. Best wishes!

Related Posts: