Mastering Bubble Sort in Java

Have you ever needed to sort a collection of elements in Java? One of the simplest sorting algorithms you may come across is Bubble Sort. In this article, we will explore the inner workings of Bubble Sort, look at its implementation in Java, discuss its performance, and optimize it for better efficiency.

Understanding Bubble Sort

Bubble Sort is a comparison-based sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The pass-through of the entire collection is repeated until the collection is sorted.

Let’s understand the algorithm with an example:

Suppose we have an array of integers: [5, 3, 1, 4, 2].

1. In the first pass, adjacent elements are compared and swapped if necessary. The largest element “5” is bubbled up to the end of the array. The updated array becomes [3, 1, 4, 2, 5].
2. In the second pass, we compare and swap again. The next largest element “4” moves to the second last position. The array becomes [3, 1, 2, 4, 5].
3. This process repeats until the array is completely sorted.

Bubble Sort follows a simple rule: the largest element “bubbles” up to its correct position in each pass.

Implementing Bubble Sort in Java

Let’s see how we can implement Bubble Sort in Java:

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

In this implementation, the outer loop runs (n-1) times where n is the length of the array. The inner loop runs (n-i-1) times because after each pass, the largest element is already in its sorted position.

Performance and Optimization

Bubble Sort has an average case and worst-case time complexity of O(n^2), which makes it inefficient for large datasets. However, in certain cases where the input is nearly sorted, Bubble Sort can have a better time complexity of O(n).

To optimize Bubble Sort, we can introduce a flag variable swapped, which keeps track of whether any swapping occurred in a pass. If no swapping occurred, it means that the array is already sorted, and we can terminate the sorting process early.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                // Array is already sorted, terminate early
                break;
            }
        }
    }
}

By adding the swapped variable, we reduce unnecessary iterations and improve the performance of Bubble Sort in certain cases.

Conclusion

Bubble Sort may not be the most efficient sorting algorithm for large datasets, but it provides a straightforward understanding of how sorting works. Implementing Bubble Sort in Java is a great exercise to grasp the concept of comparison-based sorting algorithms. Additionally, optimizing Bubble Sort by introducing a flag variable can improve its performance in certain scenarios.

So the next time you need to sort a collection of elements in Java, consider Bubble Sort and its optimizations to achieve the desired performance.