Wednesday, April 27, 2016

A Silly Mikstake ... Selection sort


Did you ever do a mistake and suffer the consequences? And feel guilty of your predicament? In that moment of guilt, you decide that you are not going to do that mistake ever again. You are full of confidence that sure as hell, you are not going to repeat it again. It was a pain in the @$$ after all.

As time passes, you forget the consequences altogether and you are there again. Where? Yeah right there, in the little predicament of yours :). What would this be called? A silly mistake, right? and what would you call yourself? Silly of course.

In the last post we met bubbly and saw how crazy she is about chocolates. Yeah yeah I know you went through all that pain to get her out of trouble. There she is again. Yeah that's why we call her silly now.




Last time when we rescued bubbly, the ordeal she went through was tough on her and us alike. A lot of swapping around in her belly. And if we have to do it again and again, we must find a better way to deal with it.

So this time I needed to look for a solution which was a bit smarter and less painful. I looked around to see if any smarter way already exists. To my surprise, it was there all along. I myself must have used it in my childhood. You too must have used it or at least seen it working.

Baffled? Don't Be!

Ever seen how a kid selects her/his chocolate when presented with multiple options?

When it comes to chocolates, kids have two things in common:
  1. They want the biggest(Bigger the better).
  2. They don't trust the world around.
So in this untrustworthy world of adults, how would a kid get the best and biggest chocolate she can? Trust me, kids know better. So lets say a kid is presented with the same chocolates that Silly (a.k.a Bubbly) ate.

The kid would anyway grab the first chocolate she gets. She will hold on to it tight (as if the world is against her. I love the look on the face of a kid at that moment. Who doesn't? ) while she compares it with the next available chocolate. 

And if she finds another chocolate bigger than the one she already has, she will grab that chocolate. But wait, technically the kid has not decided on the chocolate yet. She will continue to grab the chocolate she thinks is bigger than the earlier ones. So at the end, when she has the biggest chocolate with her, she will then give up the small chocolate(Yeah I know, she wont give anything back).

The analogy may not be 100% accurate or correct, but it conveys one important method to sort. Selection sort. Well it revolves around selecting the right candidate.

Lets summarize the steps:
  1. Grab the first item you get.
  2. Compare it with the rest of them looking for the smallest item(Note: I hope you are not a kid and won't always go for the motto: The bigger the better).
  3. Swap only at the end when you know that this is the biggest smallest item.
Lets apply a child's mind and see how far we can go:

The problem and the goal are similar to the last time. Here they are for your quick reference:

The problem: Silly has eaten chocolates out of order (AGAIN!!!!!) 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 Silly as shown in the following image:



Operation rescue Silly again begins

Agreed that misplaced chocolates in Silly's tummy are painful to her, but so are frequent swaps. Our goal here is to relieve Silly out of her pain with less pain in the process.

So as usual we start with the first(smallest) scale. Mark the first chocolate(3). Hold on to it temporarily. I did not mean to get technical just yet but for ease of association, you can relate it to putting the first chocolate in a temporary variable and marking it's scale for future reference. As a kid, you hold this chocolate in your left hand. Thats much better to imagine. :)

The situation looks something like this:




Now lets compare this chocolate(temp = 3) with the chocolate in the next scale(2). As 2 is smaller than 3, we release the value 3 and grab chocolate 2 making temp = 2. We also change our future reference mark.


Next, compare temp = 2 with the chocolate in the third scale(5). 5 is greater than 2 so we are good here. No changes and we move on.


Next we compare temp = 2 with the chocolate in the forth scale(4). 4 is greater than 2 so again no changes. Lets move on.


Lets compare temp = 2 with the chocolate in the fifth scale(1). 1 is smaller than 2 so we need to change the chocolates. grab 1 in the left hand or make temp = 1 and yeah, don't forget to mark the scale for future reference.


This was our last element and hence, we have completed our first pass through Silly's scales and we have found the smallest chocolate which will go in the first scale of Silly. So just one swap here. Swap the chocolate in the first scale(3) with the one in the marked scale which happens to be the fifth scale in our case.




So after our first pass through Silly's stomach, we have put the smallest chocolate in the smallest scale, and that too using only one swap.

As the first 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 forward. So Silly starts feeling much better after each pass with fewer swaps. See below the improvement in Silly's condition after each pass:

Pass 2:


Pass 3:


 I have deliberately not highlighted the swapped scales here. If you are really interested, you would find it out by doing the mental passes yourself. That should ideally strengthen the understanding.

Pass 4:


Pass 5:



As you can see, Silly has got her relief just after the third pass, but still our algorithm has no way to find it out. It has to continue with the passes, although no swaps will be needed.

Now, hopefully you are clear with the steps required to do a selection sort on a bunch of numbers. You already knew that. Just needed some association.

As you must have also noticed, when we helped Bubbly out of her trouble last time, each comparison could cause a potential swap. So if we consider the worst scenario where the items are arranged in an exactly opposite order, each comparison in each pass would require a swap.

While here, when we rescued Silly, we did just one swap in one pass through Silly's tummy. Even in the worst case, we would require a single swap in one pass. And there may be passes where we don't even do a single swap. This drastically reduces the number of swaps required.

Hence, even though the number of passes and comparisons in both Bubble sort and Selection sort tend to be on same lines, the number of swaps is drastically reduced in Selection sort.

As usual, write your own code, be creative, associate with your personal life and recall periodically and most importantly, have fun!

Will Silly repeat her mistake again? Will we be able to rescue her again? Will we be able to reduce the troubles she goes through each time? To find out, stay tuned.

Did you know?

While I was deciding the names for my caterpillars, I thought lets name then based on the sort algorithms, so for Bubble sort, I had Bubbly, for Selection sort, I initially chose Sili and for insertion sort I chose XXXXX (We are not there yet :P) . Although finally Silly better suited her personality. Just out of curiosity, I did a Google search on Sili and found out some amazing facts:

In a country called Samoa (I did not know there was a country named Samoa), there is a village called Sili.

And by the way, Samoa is home to the Flying fox. The bat. Yes bat, Bat, BAT, The Bat, THE BAT....come on you know I love bats :).

The large flying fox is among the largest species of bat. It weighs 0.65–1.1 kg (1.4–2.4 lb) and has a wingspan of up to 1.5 m (4 ft 11 in). Its head-body length is 27–32 centimetres (11–13 in) - source is our beloved Wikipedia.

After all, learning does lead to more learning.

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

Until then,
Happy Learning!
Banyan Bat

2 comments:

  1. no doubt selection sort approach is a less painful remedy than bubble sort for Silly..but lets see if doctor banyan bat can think even more painless therapies for Silly because from all we know Silly aint gonna stop hogging on chocolates mindlessly :-)

    ReplyDelete
    Replies
    1. hehe ... yeah... soon it will become more pain for us than her. :) She is like a drunkard who enters a deadlock in search of the high...You gave one more clue which can be used to make the deadlocks of threads an interesting topic after all :P

      Delete