Bubble Sort Algorithm

Bubble Sort algorithm derives its name from the fact that it results in the largest element to pop out in every iteration. It does so by repeatedly swapping adjacent elements if those are out of order until no more swaps are required.

Consider the following input: [3,5,1,9,8,7] and let’s try to trace the bubble sort steps on this input:

First Pass

1. [3,5,1,9,8,7] : no change as 3 and 5 are in correct order.
2. [3,1,5,9,8,7]: 5 and 1 are swapped to ensure the correct order.
3. [3,1,5,9,8,7]: no change as 5 and 9 are in the correct order.
4. [3,1,5,8,9,7]: 9 and 8 are swapped to ensure the correct order.
5. [3,1,5,8,7,9]: 9 and 7 are swapped to ensure the correct order.

After the first iteration, the largest element will be at its correct position. Similarly, after the second iteration second largest element will be at its correct position and so-on:

1. Second Pass: [1,3,5,7,8,9]
2. Third Pass: [1,3,5,7,8,9]
3. Fourth Pass: [1,3,5,7,8,9]
4. Fifth Pass: [1,3,5,7,8,9]

Continuing the swapping mechanism for n number of times (n being the input size), we can get a sorted output by correctly positioning one element in every iteration.

Following is a java based implementation of this approach:

public void sort(int[] input){
    int length = input.length;
    for(int i = 0; i < length - 1; i++){
        for(int j = 0; j < length - 1; j++){
            if(input[j] > input[j + 1]){
                int temp = input[j];
                input[j] = input[j + 1];
                input[j + 1] = temp;
            }
        }
    }
}

Here we compare the adjacent elements and swap those if found out of order. The worst-case complexity of this algorithm is \(O(n^2)\), which is unsuitable for inputs of significant size.

The example that we chose highlighted a significant drawback of this implementation. After the second iteration, we can see that the input was already sorted. But, even then, the algorithm continued to iterate the input.

We can update the algorithm a bit and can break the loop if, in any iteration, no swaps were made. Having no swaps in any iteration indicates that all the elements are in the correct position now, and we can terminate the loops.

We can include another optimization to this algorithm based on the fact that in every iteration, the current largest element will be at its correct position (the rightmost available slot), which means, we can skip that slot in the next iteration (i.e., last i slots can be ignored in \(i^{th}\) iteration)

An updated version of the same algorithm with these two improvements is mentioned below:

public void sort(int[] input){
    int length = input.length;
    boolean unsorted = false;
    for(int i = 0; i < length -1; i++){
       // decrease the upper bound by a factor of i
       // in every iteration to skip the rightmost sorted slots
        for(int j = 0; j < length - 1 - i; j++){
            if(input[j] > input[j + 1]){
                unsorted = true;
                int temp = input[j];
                input[j] = input[j + 1];
                input[j+1] = temp;
            }
        }
        // if no swaps were made in the last iteration
        // break the loop
        if(!unsorted){
            break;
        }
    }
}

These optimizations reduce the number of comparisons by a significant margin, although the number of swaps required to sort the input remains as is.