the cedar ledge

Insertion Sort

Date: December 19 2020

Summary:

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

Bibliography

Not Available

Table of Contents

    1. Technical Definition
    2. Discussion
    3. Plain-Word Explanation
    4. Code Implementation
  1. How To Cite
  2. References
  3. Discussion

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][5, 2, 4, 6, 1, 3] - ugh! These are not in order!

I instantly set to organizing my hand by first switching 55 and 22. I then see that I can switch 44 and 55. I don't need to switch 66 as it is bigger than 55 - great! However, when I come to 11, I know that 11 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 33 - drat, this is a pain - I have to scan the previous cards in my hand before 33 and see that it goes after 22.

Hooray! I now have a sorted hand of [1,2,3,4,5,6][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

CC BY-SA 4.0 Jacob Zelko. Last modified: May 19, 2024. Website built with Franklin.jl and the Julia programming language.