Bubble Sort Algorithm: A Complete Guide with Java Code

Bubble Sort is a simple yet fundamental sorting algorithm that has been widely used in various applications. Despite its simplicity and inefficiency for large datasets, Bubble Sort is a great starting point for learning the basics of algorithmic thinking and problem-solving. This blog will walk you through the philosophy behind Bubble Sort, its working principle, and how to implement it efficiently in Java.

What is Bubble Sort?

Bubble Sort is a comparison-based algorithm that organizes a list by continuously swapping adjacent elements whenever they are in the incorrect order. The name “Bubble Sort” comes from the way smaller elements “bubble” to the top of the list, much like air bubbles rising through water.

While it may not be the most efficient sorting algorithm, it is easy to understand, making it a good educational tool for beginners.

Philosophy Behind Bubble Sort

The philosophy of Bubble Sort is based on the principle of incremental improvement. It ensures that with each complete pass through the list, the largest unsorted element gets placed in its correct position. This process repeats, gradually bubbling up the next largest elements until the entire list is sorted.

Here’s a step-by-step outline of the thought process behind the algorithm:

• Comparison: Compare adjacent elements in the array.
• Swap: If the current element is greater than the next, swap them.
• Iteration: Repeat this process for each pair of adjacent elements.
• Pass: After every full pass, the largest element in the unsorted section is placed in its correct position.
• Repeat: The algorithm repeats the process for the remaining unsorted section until the entire array is sorted.

Working Example of Bubble Sort

Let’s consider a simple example to explain how Bubble Sort works.

Unsorted Array:

[5, 2, 9, 1, 5, 6]

Pass 1:

• Compare 5 and 2 → Swap → [2, 5, 9, 1, 5, 6]
• Compare 5 and 9 → No Swap → [2, 5, 9, 1, 5, 6]
• Compare 9 and 1 → Swap → [2, 5, 1, 9, 5, 6]
• Compare 9 and 5 → Swap → [2, 5, 1, 5, 9, 6]
• Compare 9 and 6 → Swap → [2, 5, 1, 5, 6, 9]

After the first pass, 9 is in its correct position.

Pass 2:

• Compare 2 and 5 → No Swap → [2, 5, 1, 5, 6, 9]
• Compare 5 and 1 → Swap → [2, 1, 5, 5, 6, 9]
• Compare 5 and 5 → No Swap → [2, 1, 5, 5, 6, 9]
• Compare 5 and 6 → No Swap → [2, 1, 5, 5, 6, 9]

Now, 6 is placed in the correct position, and so on.

The process continues until the entire array is sorted.

Time Complexity of Bubble Sort

The worst-case time complexity of Bubble Sort is O(n²), where ‘n’ is the number of elements in the array. This is because, in the worst case, the algorithm needs to go through ‘n’ passes, and for each pass, it compares ‘n’ elements.

• Best-case scenario: O(n) — occurs when the array is already sorted.
• Average-case and worst-case scenarios: O(n²) — occurs when the array is randomly ordered or reversed.

Because of its quadratic time complexity, Bubble Sort is inefficient for large datasets.

Java Implementation of Bubble Sort

Now that you understand the basic idea behind Bubble Sort, let’s move on to its Java implementation. The code below demonstrates how to implement this algorithm in Java.

public class BubbleSort {

    // Function to perform Bubble Sort
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        // Outer loop for each pass
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // Inner loop for each comparison
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap if elements are in wrong order
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no two elements were swapped, array is already sorted
            if (!swapped) break;
        }
    }

    // Function to print the array
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2, 8};

        System.out.println("Original Array:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);
    }
}

Optimizations for Bubble Sort

While Bubble Sort is not the most efficient sorting algorithm, it can be optimized slightly by introducing a flag that breaks out of the loop early if the array is already sorted. In the above Java implementation, the swapped variable tracks whether any swaps were made during a pass. If no swaps occur, the algorithm terminates early, as the list is already sorted.

Why Learn Bubble Sort?

While Bubble Sort is not practical for large datasets, it is still widely taught for several reasons:

• Simplicity: Its step-by-step approach is intuitive and easy to grasp.
• Foundation: It helps build the foundation for understanding more complex sorting algorithms like Merge Sort or Quick Sort.
• Educational Value: Bubble Sort introduces key programming concepts like loops, conditionals, and optimization.

Conclusion

Bubble Sort may not be the fastest sorting algorithm, but it plays an essential role in understanding how algorithms work. The step-by-step approach of comparing and swapping elements lays the groundwork for tackling more advanced sorting techniques. Implementing Bubble Sort in Java is straightforward, and understanding its optimization can help you grasp fundamental algorithmic concepts.

With its clear logic and easy-to-understand structure, Bubble Sort remains a key algorithm for learners and programmers alike.