Banyan Bat: Bubbly goes to Las Vegas

"I got a letter from the guy who stole my identity. He says he's giving it back, because ever since he took it, he hasn't been able to win one hand at poker"

As you already know by now Bubbly is cute. You also know that she had a thing for chocolates and suffered her share of consequences of over indulgence. She learnt her lessons and she has now learnt to control her urge for chocolates. Now she is always this beautiful smiling small Bubbly:

So no more rescuing Bubbly from her troubles. Well, hold on! Some people have this thing for troubles. They know all the means to get into trouble. Bubbly is one of them. :) But after all, she is our cute little Bubbly. We gotta save her.

Looks like Bubbly has gone too far in celebration of her happy times. Last time Bubbly was seen, she was playing poker at The Venetian, Las Vegas.

As you already know, Bubbly has issues with arranging things in order. So to help Bubbly win, our job is to make sure that she holds her cards in order and of course, hides them well from the fellow players. Considering that I am the worst Poker player, that is all I can do to help her here.

The approach that we are going to use today to rescue Bubbly out of her newfound trouble is again something that has been around for ages and people from all the walks of life and age groups must have used it sometime in their lives.

Okay, let me come straight to the point. If you have played any cards game, you have used this technique.

Yeah, Don't give me that poker face now, I know you have been playing cards, behind the back of your parents. Don't worry. Chances are, they had done it too when they were young. :P

So, let me first congratulate you as you already know this technique and you don't even need to learn it. OK, don't be too relaxed as well because we still need to do some work. We need to draw upon our memory reserve and turn it into something Javaish, Cish, C++ish.....you get the point.

Lets say, Bubbly has following cards in her left hand:

Our job is to help Bubbly arrange these cards in ascending order for ease of access.

Step 1:

Bubbly has got a 3 of heart as the first card, next she has got a 2. Okay, so lets take this 2 out into the right hand.

Step 2:

3 is bigger than 2, so let me first move 3 one position right.

Step 3:

Now let me put 2 in the empty space.

Step 4:

5 seems to be Ok as far as its left side is concerned.

Step 5:

4 is less than 5. Or looking at the cards on the left, there is one card (5) bigger than 4, so let me grab 4 in the right hand.

Step 6:

5 is bigger than 4 so let me move 5 one position right.

Step 7:

3 is less than 4, so let me put 4 in the empty position just to the right of 3.

Step 8:

Looking at the cards on the left of 1, starting from the immediate left card, we can see that these cards are bigger than 1. So let me take 1 in my right hand.

Step 9:

5 is bigger than 1, so let me move it one position to the right. 4 is bigger than 1, so are 3 and 2. So all of them have to move one position right. Making the cards in the left hand look something like this:

Step 10:

There are no more cards on the left, so let me put 1 in the empty spot.

Here's our sorted hand of cards. Now no one can stop Bubbly from winning this Poker game.

This is nothing but insertion sort, because you are inserting each element in its sorted position.

Lets label a few things for creating our Insertion sort Algorithm:

Starting from the second element, put each element into the already sorted array on the left, in its sorted position.

To do this, we keep each element in a temporary variable, compare it with each element in the already sorted array and until we find an element smaller than the element at hand, we keep moving them one position to the right. When we get our smaller element, we put the element in the temporary variable, just after the smaller element.

Insertion sort is now under your belt.

Your little knapsack of Data Structures and Algorithms now looks something like this:

Can you compare these three sorting algorithms? Can you find out which one is the better? Ask as many questions as you can ask. Here are a few for starters:

What is common among these three algorithms?
Is one faster than other?If yes, which one?
Is one simpler than other?
What happens if the array is too big or too small?
What happens if the array is already sorted?
What happens if the array is reverse sorted?
What is not so common among them?

As a teaser trailer to these questions: The biggest difference between Insertion sort and the other two sorting methods we saw is that, insertion sort does not do a swap.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat