Reviewing Sorting Algorithms: Bubble Sort

Let’s sort it out!

In this series of posts, we will be discussing basic computer science algorithm sorting techniques. Yes, you are right we are here again trying to shake up our memory boxes for these algorithms long forgotten. Recently, I attended an interview for a Silicon Valley company, and you guessed it right, KO (Knock Out) coding rounds were the appetizers and I figured pretty much on my day 1 of coding interview preparation, that I'm not serving KO’s back on coding challenges.

You may most definitely choose to agree with me that we always remember the most popular and unpopular of everything. I was sure the most unpopular sorting technique was “Bubble Sort” and the popular one was “Quick Sort”. Basically, my statement is incorrect on many counts about the popularity of the sorting techniques, the most unpopular kid in your high school is pretty much popular for being not so.

Why is sorting a big deal?

We know sorting things almost in every instance reduces the complexity of the problem at hand. Sorting is a well-solved problem in computer science, It puts any list coming out of a computer into a certain required order efficiently to reduce the searching complexity of the problem.

In a series of posts, we will be discussing some of the sorting algorithms listed in the below order:

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Merge Sort

5. Quick Sort

6. Heap Sort

Let’s start with the most popularly known Sorting technique. You are getting better at the game of “who’s more popular!”

Bubble Sort

Bubble sort is a very simple comparison-based algorithm used to sort the elements which are out of order. It compares the two elements at a time to check for the correct order, if the elements are out of order they are swapped. The swapping of elements continues, until an entire sorted order is achieved. Although a naïve algorithm, knowing bubble sort helps in understanding the technicalities of sorting in comparison with other techniques.

Let’s play with the bubbles.

Problem: Sort the numbers 10, 4, 8, 6, 1. As mentioned earlier, bubble sort will compare the two pairs at a time.

Let’s start with the first iteration of the numbers:

Rinse and repeat! Until the required sorting order is achieved. This begs the question, what if the problem has a very long list of elements to be sorted like for example 100 or 1000? Well, the number of iterations to check every pair of elements repetitively might exhaust you (n-1) times. Which means, it will take (n-1) iterations in order to sort a list of n elements. Mind you, the above example was just the very first iteration and for n=5, it takes a total of 4 iterations to complete the sorting.

2nd Iteration:

3rd iteration:

4th iteration:

Observations based on Iterations:

• ‘n’ number of elements will undergo (n-1) iterations to complete the sort.

• If you have noticed, the max number in the list 10 is placed in its ordered position after the first iteration.