Banyan Bat: Operation rescue Bubbly - Bubbly bubbly bubble sort...

The Bubbly Fish

Remember the caterpillar we met in my 3rd post? I loved it so much that I decided to adopt one. Today we meet Bubbly.

Bubbly - The Caterpillar

We are going to talk a lot about Bubbly. So you better start liking her :). By the way, Bubbly likes to eat a lot of chocolates and when she gets hold of some, she can't control. So while I was preparing for this post on this sunny Sunday morning, I had some chocolates lying around on my table.

Help yourself....

While I was involved deeply in writing this post, Bubbly somehow got onto my table and eat all these chocolates. Remember? Bubbly has those scales which get smaller and smaller at the end. She is better off if she eats small stuff first and then large stuff so that small stuff goes to the small scales and large stuff remains in the large scales. But she is crazy when it comes to eating chocolates, who isn't? She ate them hurriedly in quite the opposite order and see what she has turned herself into:

Now she has to do a lot of work to get her back in shape. Lets see what is her problem and if we can help her get out of it.

The problem: Bubbly has eaten chocolates out of order causing her scales to be stretched. This is painful and uncomfortable for her.

What needs to be done: We need to find a way to rearrange the chocolates in such a way that the smallest chocolate is in the smallest scale and the largest chocolate is in the largest scale: What we want is a happy Bubbly as shown in the following image:

Operation rescue Bubbly begins

Larger chocolates in the smaller scales would be more painful. Our goal is to make Bubbly as much comfortable as we can. So lets start by moving the largest chocolates to their suitable scales so that Bubbly starts getting the relief she deserves as quickly as possible.

Lets start with the first(smallest) scale. Compare the chocolate in the first scale with the one in the next scale and swap them if the first one is larger than the next one. As you can see, the first scale has chocolate 3 while the scale next to it has chocolate 2. 3 is larger than 2 so lets swap them. Luckily Bubbly is so flexible that we can comfortably swap the contents of the adjacent scales without too much trouble.

So now Bubbly is a bit relaxed and looks something like:

As you can see, even though she is relaxed a bit, she still needs a lot of swapping and shuffling before she can be happy. Lets continue with our effort by comparing chocolate in the second scale with the one in the third scale. 3 is smaller than 5, so for now we can leave these two chocolates at their places and move on. At this point there is no change in the position of chocolates and hence no further relief to Bubbly.

Now lets compare the chocolate in the third scale(5) to the one in the forth scale(4). Now 5 is greater than 4 so lets swap. Bubbly is further relieved a bit.

Lets now compare chocolate in the forth scale(5) with the one in the fifth scale(1). Obviously 5 is greater than 1 so swap again.

As you can see, the largest chocolate (5) is now in the scale where it belongs. Somehow in our first run through all the chocolates, the largest chocolate has bubbled out to its proper position. That is the reason this type of sorting is called Bubble sort and we performed it on Bubbly.

As the last scale is already sorted, in the next move we will only pass through unsorted 4 scales and then in the next pass only through 3 scales, subsequently sorting chocolates backwards. So Bubbly starts feeling much better after each pass. See below the improvement in Bubbly's condition after each pass:

Pass 2:

Pass 3:

Pass 4:

I have tried to be a bit creative with bubble sort as we discussed in the Step 7 of my first post. Our brains are made such that a slight hint of novelty and a bit of association to what we already know are usually enough to keep us hooked.

A few other simple tricks that can help you recall this logic are:

As shown in the first image, imagine the bubbles coming out of water slowly and in steps. Imagine the bubbles talking to adjacent bubbles and swapping if required. I am not joking, literally imagine them talking to each other. Imagine huge ocean of coke (or beer) if you like. This will help you remember that swapping happens after each comparison (if required).
Imagine the bubbles coming out of the ocean and bursting away. This will help you remember that for each pass, the last item is already sorted and bubbled out. So you don't consider these sorted items in the subsequent passes, sorting your array backwards.
Close your eyes and see it. Its fun!

Now, hopefully you are clear with the steps required to do a bubble sort on a bunch of numbers. Go ahead and try to write your own bubble sort in a language you like (C, C++, Java, PHP or any other language of your choice). Run your program thoroughly and work out various inputs. This is your feedback.

Create your own version of bubble sort scenarios. Try to apply it everywhere. Go grab your pack of cards and take all the hearts and shuffle them and then sort them using bubble sort.

Come back to your algorithm and associations after some time. Never reread the algorithm. Always recall it from memory. If you have forgotten, try harder. The harder you need to try, better you will remember it (only if you keep at it). Okay, relax! If you really can't recall, go ahead and re-study.

These steps may sound like too much for bubble sort. I know :). But its a habit and pattern that we are forming here which I hope will help us conquer the complex ones when we get there.

Let this awesome algorithm settle down in your mind while you do something else that's fun for you.

As you can recall from the bubbles coming out of the ocean, this algorithm does a swap every time it compares two elements (I am considering the worst scenario here when each comparison requires a swap). If the array is too large, it could mean a lot of swaps. Can we improve it? Is there anything better than a bubble in the beer? Lets find it out in the next post.

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

Until then,

Happy Learning!

Banyan Bat