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