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

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:

1. 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).
2. 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.
3. 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

You are searching so hard, that you have lost yourself

"Keep looking and keep searching and then out of nowhere you will find what you have been looking for, But only when God believes you are ready." - Karen Kostyla

Now that might be a nice quote for life, but in the world of algorithms, this is exactly what we call an infinite loop :) and we don't want to get trapped there.

Lets say, in a more practical scenario, we have a simple array like the one depicted in the following diagram and we want to search the element 1. Being completely oblivious about the arrangement of elements in the array warrants a look at each element to search for the element we want. After all a computer is nowhere close to human brain. It needs instructions for every #$%^&*@ thing.

A sample Array

Its like searching for a house in a city without the address. You have to look at every house until you find the one you are looking for.

To understand the solution to this problem, lets first go through a small story.

In a hypothetical village called Algoville, there is a bridge that divides the village into two areas namely Funville and Dumbville. (The names here are purely fictitious. Any resemblance to any suburb is purely a coincidence.)  ... only people in Mumbai can relate.. :P).

Algoville

So when somebody tells that she/he is from Algoville, first thing people do is ask them, so are you from Funville or Dumbville? The answer to this simple question gives the villagers a clear idea about where she/he lives(almost).

This is possible because the bridge lets the villagers have a rough idea about the arrangement of the village.

So, if we know the arrangement of numbers in the above array, would it help us locate our number (The number 1, we are looking for) any faster? Let's not answer it yet.

We are looking for:

arrangement of numbers in a particular order.

This is nothing but the definition of sorting. So if we can sort the array, we can build our bridge and actually we can keep building bridges until we are left with only one house on each side of the bridge. First thing first. Lets sort the array.

There are quite a few sorting algorithms out there in the world and each one has its own pros and cons. A few of them  are listed below:

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quicksort
• Heapsort
• Shell sort

A more detailed list of an infinite number of sorting algorithms is a google away :).

Our goal will never be to complete all the sorting algorithms (or a complete list of any algorithms for that matter). I believe that learning is fun when you are moving forward and exploring stuff. So rather than focusing on an entire list of sorting algorithms at one time creating a plateau and then moving on to the next type of algorithms (if we ever finish all the sorting algorithms), we will only learn a few simple sorting algorithms. (Hell !! that was a long sentence. Took my breath away :P) So that we are able to perform sorting and have some options to choose from. Once this is achieved, we will move on. Later as we learn new things, we will come back to add to our little knapsack.

This seems to be a very smart way of avoiding all the hard work involved in learning all those sorting algorithms and then remembering them forever. Oh yeah it is!! But after all its SMART right? We can maintain interest in the subject if we are learning new things and if our brain thinks it has gone from place A to place B. Trying to master everything in one area may not give this feeling and more importantly, we may never achieve the goal if we are stuck with the keyword "everything".

The goal is to keep things simple as much as we can and keep moving. They say things are not easy or tough as such. Its a matter of patience,practice and perseverance. All the legends in their own fields seem to do all sorts of things effortlessly. That's because they have made those things easy for them with endless sessions of careful practice and focused effort. I don't have personal experience to back that last sentence. And the main goal of this series of blog posts is to see if I can be persistent. These blog posts are nothing but chronicles of my efforts towards applying the above principle to the things I fear most. I started with Algorithms and Data Structures.

We will work on the first three sorting algorithms, namely Bubble Sort, Selection Sort and Insertion sort. Then we will move on to our next data structure and come back as we learn more strategies.

This post was small. Originally I wanted to include bubble sort in this post. But I avoided that for two reasons.

First, I have been procrastinating on the 2015 Tax returns and now the deadline is hanging over my head. No matter how early they start advertising and informing us, somehow I always end up doing it at the last moment. I need to improve that.

The second reason is: I preferred creating a stage for the necessity for sorting in this post and then writing a post for each sorting algorithm. That way we have a reason for learning to sort. Its usually easy to learn a new thing if you can trick your brain into thinking that its a crucial task.

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

The next three posts will be dedicated to Bubble, Selection and Insertion sort - in that order.

Until Then,

Happy Learning!

Banyan Bat

Meet the Caterpillar....Data Structures Begins...

"And whats a butterfly? At best, He is but a caterpillar, at rest." - John Grey

"To become a butterfly, you must first start as a caterpillar."

You must be wondering, why the hell is he writing about caterpillars and butterflies in a post that claims to talk about data structures. I believe there are a few things about the caterpillar that will help us understand and remember today's data structure.

About Banyan Bat - A Statement of Purpose..

"In every Job that must be done, there is an element of fun" - Mary Poppins

Banyan Bat is a relentless learner who wants to share how he is learning new stuff and how its changing his life. Like everybody else, he fails. But he believes learning is easy if failure is considered as one of the steps in learning.

Banyan Bat also believes that every area of life needs learning and its fun, no matter how simple or easy the achievement is.

You would ask, why Banyan Bat?

Banyan Tree signifies longevity, strength and wisdom and last but not the list, is the national tree of India :)

The Bat is the batman from Christopher Nolan’s Batman trilogy. Batman has always been my Superhero. Now, in the Superman Monologue from Kill Bill Volume 2, Bill quite grippingly convinces the bride that Superman is the only real superhero because he was born with all the skills and strengths he has. I on the contrary, believe, thats what makes Superman even more ordinary. He is no different from a kid to a rich businessman who knows all the ways to spend money. After all he was born with that money. 

Batman on the other hand chose to be something more than he was born to be. I believe thats what makes one a hero :).

Banyan Bat is willing to mix the wisdom of the mighty Banyan Tree and the agility and intention of Batman.

This is an intermediate post because an introduction to Banyan Bat and a clear statement of purpose was in order.

"Have no fear of perfection, you will never reach it." - Salvador Dali

Banyan Bat does not claim to be an expert in anything he writes about and the main purpose of this blog is to share the tricks he uses to make it fun to learn new things. None of the posts aim at being a complete tutorial for the subject under consideration. Though they do humbly and honestly try to be an aid in understanding and remembering the subject at hand.

Your inputs and invaluable suggestions are not only welcome but are much needed in this endeavour.

You can visit my latest post here.

Happy Learning!!!
Banyan Bat

How I made Data structures my Friends and Algorithms my girlfriends - Bruce Wayne Style ...

If you are a software engineer, you must have known some data structures and some algorithms. If you are like me, you must be afraid of those words.

Yes, a lot of people (we would some times not even hesitate to say: all of us - data structure champions, please ignore my blissful ignorance and forgive me), hate those words. We kind of feel scared of the whole concept of data structures and algorithms.

I am a software engineer. And I had data structures, algorithms and their analysis as a core part of my curriculum.  I would not lie, I was hardly able to understand most of it. It was all like gibberish to me at that time.

I have been writing software (or at least working in a software company :P) for more than 10 years now and I still get goosebumps when I hear those words. I knew something was not right and needed to be changed. Hence I was always on the lookout of a way to make these things (now my beloved) stick around my head. I searched internet, surfed websites and blogs, listened to videos in search of a superhero trick to understand data structures in a ninja style, just like Bruce Wayne was searching for a way to fight injustice in Batman Begins :).

As simply killing the offender does not mean justice, reading and memorizing data structures and a few algorithms around these data structures will not sail us across. We need to kill the real beast. A deep understanding of basic data structures and algorithms and a way to build our own data structures and algorithms using this base is the ultimate goal. Lets see how far we can go.

Following are the steps I came up with which I am trying to follow to move towards our goal in the step by step manner. I believe, these steps can make you potentially learn anything quickly and make it stick forever. but for now, lets apply them to data structures and algorithms.

Step 1: Start small and basic

Even the mighty Banyan Tree stars as a seed. :)

• Start with the easiest, smallest and simplest data structure
• Understand the ins and outs of this easiest data structure and operations you can perform on this data structure.
• Try to avoid calling these operations algorithms if that word gives you nightmares :P

Step 2: ADT: Abstract Type Data...??? Nope, wait, I mean Attention To Detail..

Focus!! Focus!! Focus!!

• Ridiculously focus on the details of this small data structure.
• Understand how it works, what are its key features. Live with the data structure day and night. Become desperate to understand it exactly as Bruce Wayne was desperate to fight criminals to the point that he locked himself up with the criminals to understand them.
• Understand the limitations of this data structure so that you have the reason to look for a better data structure if at all it exists( as of now you are not aware of anything else in the world).

Step 3: Theatricality and Deception are powerful agents...

Theatricality add the much needed spice to your learning!

• Devise your own personal situations/tools/scenarios where you can apply this data structure in a most dramatic way you can think of 
• Attach them to something really personal to you...

Step 4: In your own words...

• Write about the data structure in your own words.
• Create your own problem statement and your own solution
• Create a data structure workshop like the one Bruce Wayne had :) .

Step 5: Call Alfred often

• Have your own Alfred. Okay relax, you don't have to hire a butler. You actually don't even need an actual person. 
• After writing down stuff in your own words, refer the original material and confirm that you have written everything correctly. That's it!

Step 6: Engage all your senses

• See the data structure in your mind's eye, picture it.
• Hear your own thoughts on the data structure, listen to videos if you wish.

Step 7: Be creative...DIY style...

• Create something of your own that uses this data structure. Even a hand sketch would help.
• Right a song about it, paint it, use them while cooking :D
• What did you say? how can I use a data structure while cooking? haha.. thats where your creativity will come in..

Step 8: Batman Vs Superman(Recall Vs Review)

• Recall your knowledge of this data structure periodically, with exponential time gaps
• Never review or reread the material unless you have tried recalling to the point of exhaustion.
• The idea behind this recall vs reread philosophy is that you want to store this stuff in the long term memory for retrieval when you actually need it. Not in the short term memory from where it will be removed by the brain's garbage collector on the first chance it gets.

Step 9: What about escalation?

In the end scene of Batman begins, James Gordon rightly warns batman about the tough criminal (The Joker) he is about to face just after defeating one. And Batman says calmly: "I will look into it". Batman indeed succeeds in taming the Joker, after a lot of tough fights, compromises and sacrifices. 

Data structures are no different, just after you have the easy data structure under your belt, you will face the tough one, but if you keep the spirit like Batman, you would also succeed in taming all of them.

Step 10: Complexity is complex. Keep it out.

• Explore each data structure for its usefulness, use it and find out its limitations.
• Do not focus on the complexity at the beginning.
• Remember! For a learner everything is good. Learn it as a way of doing things-optional tool in your toolbox.
• You can only be sure about which tool is better by using it. 

All I am trying to say here is that try to understand the pros and cons of a data structure or algorithm by your own experiments instead of getting this information from a book (at the beginning). At this point you are not really concerned about how the data structure or algorithm will behave for a million records. Always, Start small and go big incrementally.

So, Good bye Complexity, (Not) see you soon!! Until then, go in hibernation and enjoy your lone time :)

Step 11: The most important one!!

• Do something totally unrelated to data structures and algorithms.
• Anything thats not related to data structures will do. Even if you choose to learn a new programming language, thats fine.. but really? do you have nothing else in your life? :)
• Take some other goal form your list of goals (I surely hope you have more interesting goals too) and work on it, diverting your mind away from data structures and algorithms.

I hope these steps make sense to you and help you understand data structures and algorithms as they are helping me. 

Do let me know your thoughts. All inputs are welcome and highly appreciated. :)

Next post onwards, we will start our journey through the Amazonian forest of data structures and algorithms, starting with the simplest and cutest of our friends....Caterpillar....yeah yeah I know you want to ask.....but hold your horses till the next post :)... hope you will enjoy it.

Until then,

Happy Learning!!!!

Banyan Bat.