Insertion Sort

Date: December 19 2020

Summary:

Keywords: ##zettel #insertion #sorting #algorithms #archive

Bibliography

Not Available

Table of Contents

Technical Definition

Insertion Sort: Efficient in-place sorting algorithm for a small input. Takes as an input an array A[1 . . n] containing a sequence of length n that is to be sorted. Upon algorithm termination, the input array A is sorted. [1]

Discussion

Plain-Word Explanation

Imagine playing a card game where each card in the game are numbers 1 - 10. I find it useful when playing card games to keep my cards in order from the smallest number on a card to the biggest number. I draw 6 cards and, in my hand, they are in the order of $[5, 2, 4, 6, 1, 3]$ - ugh! These are not in order!

I instantly set to organizing my hand by first switching $5$ and $2$. I then see that I can switch $4$ and $5$. I don't need to switch $6$ as it is bigger than $5$ - great! However, when I come to $1$, I know that $1$ is the smallest number in the game and I can instantly put it in the beginning and shift all the other cards in my hand. Finally, I come to $3$ - drat, this is a pain - I have to scan the previous cards in my hand before $3$ and see that it goes after $2$.

Hooray! I now have a sorted hand of $[1, 2, 3, 4, 5, 6]$ and am ready to win the game! What I just did here, is called insertion sorting!

Code Implementation

function insertionsort(input)

    @inbounds for curr = 2:length(input)
        prior = curr - 1
        while prior != 0
            if input[curr] < input[prior]
                input[curr], input[prior] = input[prior], input[curr]
            end
            curr = prior
            prior -= 1
        end
    end
    return input
end

How To Cite

Zelko, Jacob. Insertion Sort. https://jacobzelko.com/12192020184137-insertion-sort. December 19 2020.

References

[1] T. H. Cormen, Ed., Introduction to algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.

Discussion