Learning Algorithms
Tags: algorithms
Published: 2020-08-20 13:19:08

I started reading this book, [Introduction to Algorithms](https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844) to learn algorithms.

The book says

    Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table.
    To find the correct position for a card, we compare it with each of the cards already in hand, from right to left. 
    At all times the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.

    The algorithm sorts the input numbers in place: it rearranges the numbers within array A, with at most a constant number of them sorted outside the array at any time. 

I stopped reading and gave it a try in writing the algorithm. Here it goes

#### Algorithm: Insertion Sort (in my brain)

Step 1: Take one card, it's already sorted. Oh cool, can I go now? Nope.

Step 2: Take next card from the top of the deck

Step 3: Compare it against the previous card in the left hand, If the value of the card from the deck is greater than the value of the card go to Step 4 else repeat this step.

Step 4: Insert the card Go to Step 2

Cool. Is that what the book just said? The problem is in Step 4. When you play the cards, if you are normal, you don't realize the supercomputing your brain just did. 

Another problem with the approach in the book is talking about a deck of cards, but there is a sorted set of cards in my hand and a set on the table.
My brain wants to think of it as two arrays. You can solve with two arrays, but that will be really inefficient.

I used the below approach to help me visualize it as a single array and do the sorting in place.

Stick 4 cards on your 4 fingers. Leave the thump alone we need it as a place holder. 
Now do insertion sort starting from your index finger.

Step 1: Compare the 2nd card against 1st. If the value of the 1st card is less. Go to next finger

Step 2: else swap it. place the 2nd card on your thumb, move the first card to the 2nd finger, move the card from your thumb to the first finger.

Step 3: Compare 3rd finger with 2nd and 1st card. Slow down. Think you what you just said as a 150-year-old turtle. Well, I don't know how it moves. Just think one action at a time.

Step 3: Compare 3rd finger with 2nd. Did your super brain just realized, you are going to repeat Step 1 and 2. Alrite! Step 3 Take 3(film director tone).

Step 3: Compare the next finger against previous cards using Step 1. Hmm... Step 1 should be more generic. Alrite! Alrite!

### Algorithm: Insertion Sort
*When do I know I am ready! You never know. It's just a leap of faith. - Spiderman-Intro to Spiderverse*

**Step 1:** Move the 2nd card you want to compare into the `place holder`

**Step 2:** Set the position of the card you are going to compare against previous cards into `position of the card to be sorted`. 
Set `position of the card to be sorted` as 2

**Step 3:** Set `position of the previous card to be compared` = `position of the card to be sorted` - 1

**Step 4:** Check if `position of the previous card to be compared` > 0. There is at least one previous card to compare.
else, go to Step 9.

**Step 4:** Compare the card in your `place holder` against the card in `position of the previous card to be compared`. 
If the value in `place holder` is less, go to Step 5, else go to Step 

**Step 5:** Shift the card you just compared to the `position of the previous card to be compared`. 

A[`position of the previous card to be compared`+1] = A[`position of the previous card to be compared`] 

**Step 6:** Decrement the value of `position of the previous card to be compared` in order to compare the card in your `place holder` with the one before.
        
`position of the previous card to be compared` = `position of the previous card to be compared` - 1', and go to Step 4

**Step 7:** You found the position where the card needs to be inserted and shifted all the cards greater than the current card value.
Insert the card after the `position of the previous card to be compared`.

A[`position of the previous card to be compared`+1] = `place holder`

**Step 8:** if next card exists `position of the card to be sorted`+1 < array size, move the next card in the `place holder` else, you've finished sorting, go to Step 10.

**Step 9:** Set the position of the card you are going to compare against previous cards into `position of the card to be sorted`.  Go to Step 3.

**Step 10:** End

I took the leap of faith, focused on re-usability of the steps, reduced my chatter, and arrived at the above steps after several re-writes.

This is not a tutorial for the Insertion Sort algorithm. The algorithm above is one of several ways and can even be optimized further. 
If at all you want to take away one thing from this post, it is just that, 
while trying to learn algorithms, slowing yourself down and writing down your thoughts really help.

Find source code (Using Java) here.

https://github.com/arunapi/Sorting.git

Thank you for reading!