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