Understanding Bubble Sort Algorithm (with Examples in Java)

Bubble Sort is the simplest sorting algorithm. It works by repeatedly comparing adjacent elements and swapping them if they are not in the correct order. For example, if the sorting order is ascending, adjacent elements are compared, and the greater element is placed on the right. In each iteration, we compare only the unsorted elements, and the largest element is placed at the last position of the unsorted elements in the array.

The algorithm is aptly named Bubble Sort, because elements move to the right of the array on each iteration, much like water bubbles rise to the surface.

Working of Bubble Sort

Let's say we want to sort this array in ascending order

First Iteration

In the first iteration, we are trying to move the largest element to the end of the array. So, we will repeatedly compare adjacent elements, and swap them if they are out of order.

Elements that have moved to their correct position are said to be sorted.

Subsequent Iterations

This process is repeated for all iterations until the array is sorted. In each iteration, we only compare the unsorted elements, since the sorted elements are already in the correct order.

We iterate through the array n-1 times, where n is the length of the array. That is, since our array has six elements, we iterate through the array only five times. This is because, after the fifth iteration, five elements have been placed in their correct position, therefore the final unsorted element is considered sorted. After all iterations, we will have a sorted array.

Implementation of Bubble Sort

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // loop through array size-1 times
        for (int i = 0; i < size - 1; i++) {
            // loop until end of unsorted elements
            for (int j = 0; j < size - i - 1; j++) {
                // swap left and right elements if left is greater
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Running this code will print the following output to the console:

Unsorted array: [8, 2, 6, 4, 9, 1]
Sorted array: [1, 2, 4, 6, 8, 9]

In this implementation of Bubble Sort, we will iterate through the array each time even if it is already sorted. We can optimize the code further to stop sorting once the array is already sorted.

Optimized Bubble Sort

public static void bubbleSortOptimised(int[] arr){
        int size = arr.length;

        // loop through array size-1 times
        for (int i = 0; i < size - 1; i++) {
            boolean swapped = false; // track swapping

            // loop until end of unsorted elements
            for (int j = 0; j < size - i - 1; j++) {
                // swap left and right elements if left is greater
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;

                    swapped = true;
                }
            }

            // if there was no swap, then the array is already sorted
            if(!swapped) break;
        }
    }

With this implementation, if we are trying to sort an already sorted array, we will iterate only once and stop once no sorting is done.

Complexity of Bubble Sort

Time Complexity:

Best Case (O(n)):

The best case is when the input array is already sorted. The algorithm iterates through the array only once to check if it is sorted and performs no swaps.

Average Case (O(n²)):

This is when the input array elements are in random order. The algorithm must make multiple iterations and perform swaps to sort the array.

Worst Case (O(n²)):

The worst case is when the input array is sorted in reverse order. The algorithm makes n-1 iterations and performs the maximum number of swaps.

Space Complexity O(1):

Bubble Sort is an in-place sorting algorithm, that is, it does not require any extra memory proportional to the size of the input array.

Conclusion

Bubble Sort is a simple-to-understand and implement algorithm. However, it is not suitable to use Bubble Sort when working with large datasets due to its high time complexity. Use Bubble Sort when working with small datasets, or when you are not concerned with complexity.