In this first tutorial of our 'Trivial Sorting Algorithms' series, we would analyze Bubble Sort as our approach to solving the problem we set up in our introduction page.

Textual Description

With Bubble Sort, we could find the minimum value first and put it in the first index, or find the maximum value first and put it in the last. Only the adjacent elements are compared and are swapped if required. So at the end of one iteration we will have either the largest element at the end, i.e. in the highest index of the array or the minimum element at the beginning of our array; depending on the comparison and start of loop. If we started sorting the array from its smallest number, this procedure would then continue from the next index and continue iteratively until all the elements in the array have been sorted up to the highest index. Similarly for the highest index. This will become clearer from the animation below.

Note how the elements push the largest element towards the right side such that by the end of our first traversal, we know for sure that the element present in the highest index is the largest number. It is like a bubble rising from the bottom of the array such that it always contains the biggest number as it rises and finally pops creating a new surface. The subsequent bubbles cannot pass beyond that surface.

Analysis

Now let us analyze the code and determine the time and space complexity of the Bubble Sort. Let 'j' denote the current surface where the bubble would pop. For the first iteration, it would be the highest index in the array, and then, it will progressively decrease (for each popping creates a new surface). 'i' denotes the index at which the bubble currently lies.

for (int j = N; j>0 ; j--)
{
    for(int i=1 ;i < j ; i++)
    {
        if (a[i-1] < a[i])
       {
            swap(a[i-1], a[i]);
       }
   }
}

This snippet of code will definitely sort the array, but it continues to loop through and complete its run irrespective of the current state of the array. Consider the following sequence:

First Pass (outer loop)
6, 2, 4, 3, 9  → 2, 6, 4, 3, 9 
2, 6, 4, 3, 9  → 2, 4, 6, 3, 9
2, 4, 6, 3, 9  → 2, 4, 3, 6, 9
2, 4, 3, 6, 9  → 2, 4, 3, 6, 9 // only comparison but no swap

Second Pass (outer loop)
2, 4, 3, 6, 9 → 2, 4, 3, 6, 9 // only comparison but no swap
2, 4, 3, 6, 9 → 2, 3, 4, 6, 9
2, 3, 4, 6, 9 → 2, 3, 4, 6, 9 // only comparison but no swap

Third Pass (outer loop)
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap

Fourth Pass (outer loop)
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap

As you can see the array was sorted after the second pass of the outer loop, but it still continues to run until it has run its course.

Now we will try to avoid it as follows:

is_swapped = true;
for (int j = N; j>0, is_swapped ; j--)
{
    is_swapped = false;
    for(int i=1 ;i < j ; i++)
    {
       if (a[i - 1] > a[i])
       {
          swap(a[i-1], a[i])
          is_swapped = true;
       }
    }
}

after this enhancement the sequence is as follows:

First Pass (outer loop)
6, 2, 4, 3, 9  → 2, 6, 4, 3, 9 
2, 6, 4, 3, 9  → 2, 4, 6, 3, 9
2, 4, 6, 3, 9  → 2, 4, 3, 6, 9
2, 4, 3, 6, 9  → 2, 4, 3, 6, 9 // only comparison but no swap
is_swapped = true

Second Pass (outer loop)
2, 4, 3, 6, 9  → 2, 4, 3, 6, 9 // only comparison but no swap
2, 4, 3, 6, 9  → 2, 3, 4, 6, 9
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap
is_swapped  = true

Third Pass (outer loop)
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap
2, 3, 4, 6, 9  → 2, 3, 4, 6, 9 // only comparison but no swap
is_swapped  = false → exit

Though it took one whole outer loop for identifying if array is sorted or not but still better than previous version! That’s progress!

Let us see if we can further enhance it. If we observe the above-given sequence of operations, during the first pass of the outer loop, last swap operation was between (3, 6), leaving the array sorted from and beyond the swapped element i.e. 6 . The same behavior can be examined in the second pass of the outer loop as after last swap operation (3, 4), the array was sorted from and beyond 4. So the conclusion is, after one iteration of the outer loop, the array is sorted from and beyond the last swapped element i.

do {
  last = 0;
  for(int i=1 ;i < N ; i++)
  {
     if (a[i - 1] < a[i])
     {
        swap(a[i-1 ], a[i])
        last = i;
     }
  }
  N = last;
} while (N != 0)

Take a close look at the last variable as it is both shortening the loop to the last swapped element and maintaining the flag of swapping. Having enhanced Bubble sort, now we will look to the analysis of above algorithm:

1st passage through the for loop → N-1 comparison and possible swaps.
2nd passage through the for loop → N-2 comparison and possible swaps.
N-1 passage through the for loop → 1 comparison and possible swaps.

if C is the constant time required for one comparison, one swap, loop condition checking and increment of i then total time → C*( N-1 + N-2 + … + 2 + 1 )

Let K be the total cost for assignment of last and N variable and checking the condition of while, then → K(N-1) as outer loop is executed for N-1 time max

so final cost → C*( N (N-1) /2 ) + K (N-1) + K1 ~ O (N ^2)
K1 being some extra cost of initialization and other stuff.

Now the extra space complexity is → c* 1 as only one extra variable last is used → O(1).

In the next tutorial of our trivial sorting algorithms series, we will go through the Selection Sort as one of our solution to the given problem.