Sorting Problem: Bubble Sort

We saw in the last lesson the amazing applications of searching on sorted data. We realized how important structured/sorted data is such that we’re able to apply binary searching on it.

In the upcoming lessons, we will learn three strategies for sorting and their nitty gritty details.

Before we start, let’s review some important elements related to the fundamentals of arrays and their indexing,

Refresher: arrays and functions

Let’s have a refresher on arrays and how the values are passed by reference in functions.

Swap function and playing with arrays’ elements

Here is our standard swap() function:

Let’s see how the same swap() function will work on elements of arrays now!

Notice that when we pass any element of an array A[i] as a reference, an element is received while the subsequent processing on that reference changes the element that was passed as an argument.

Let’s learn our first idea of sorting, which is inspired by the bubbling process of boiling a liquid.

Sorting algorithms

Let’s look at the important aspects of the bubble sort algorithm.

Bubble sort

We know that when we boil a liquid, the molecules with higher kinetic energy go up to form bubbles. These bubbles with the highest kinetic energy then rise and escape to form water vapor. This is the inspiration for bubble sorting, whereby the elements that meet a certain condition after comparison are swapped (rise).

Discovering the famous nested loops implementation

Sample program:

       A = {6 7 8 4 3 2 1}
Sorted A = {1 2 3 4 5 6 7}

Before sorting in ascending order, let’s first understand the central strategy of bubbling behind this famous sort algorithm.

The bubbling strategy

Here is the bubbling strategy:

First, we take the start position i = 0. Then:

1. We compare the value at A[i] with its immediate next neighbor A[i]>A[i+1].
2. If the first number is greater than the second number, we exchange their positions (by using the swap() function).
3. We repeat the above two steps for the next two neighbors i = i+1, until we reach the last possible pair.

Look at the code and animation below. Look how it is working.

Look at the above animation and think about the following questions.

1. Where is the maximum element when this bubbling ends?
2. Where is the 2nd maximum element?
3. Are we done with sorting?

As you must have noticed, the above code shifts the maximum value to the rightmost position. Secondly, notice that the 2nd maximum has been knocked off by the maximum during the bubbling effect!

Of course, we are not done with sorting yet, but we have achieved one crucial step of sorting.

We have devised a bubbling strategy of making the higher values bubble up, i.e., we’ve made the higher values shift towards the right end and knock off the smaller values (in the case of descending order, the greater values will be knocked off).

Question: What will happen if we repeat this bubbling/knocking iteration two times?

Let’s look at the code below:

for(int t=1; t<=2; t++) // Repeat 2 times
{
   for(int i=0;i+1<size;i++)           
   {            // Notice i+1<size
       // Comparing two neighbors and shifting the greater to the right
       if(A[i]>A[i+1])
          swap(A[i],A[i+1]);
    }
} 

We have put the condition of i+1<size. This is because in the condition of comparing two neighbors A[i]>A[i+1], the value at i+1 will reach the boundary first; hence that should be checked for the boundary that is i+1<size.

Look at the animation below for two iterations in bubble sort:

When we repeat the knocking/bubbling procedure two times, two things will certainly happen:

1. The maximum will be at the last index of the array.
2. The second maximum will be at the second last index of the array.

That gives us the perfect direction toward bubble sort.

Implementation of bubble sort

What if we want to sort the complete array? How can we achieve that?

• Repeat the bubbling step size-1 times.

  Because the top size-1 elements are moved to the right, the last one (the minimum) is already at the 0th location. Therefore no more bubbling is needed.

So we have the following implementation:

An efficient implementation of bubble sort

Before discussing the efficient implementation of bubble sort, look at the following question.

If data is already sorted or becomes sorted during the bubbling/knocking, is there any way to make bubble sort stop early?

Yes, we can do it! Let’s see what we can do.

Improvement idea:

1. In every iteration, we maintain a bool variable changeHappen that is initialized with false before every bubbling iteration;

2. If any change happens(swapping occurs) during the iteration, then the program sets that changeHappen with true. This is the bubbling step.

3. We repeat the above two steps until changeHappen is false.

If the iteration ends and no change (swapping) happens, it means the array is already sorted.

Let’s update our implementation with the above idea.

Here is the final implementation you can experiment with in the following playground!