Bringing Bubble Sort to Life in Java

With our logical blueprint (the pseudocode) ready, it's time to translate it into a working program. This is where we shift from theory to practice, implementing the Bubble Sort algorithm in Java. We'll start with the most direct translation of our pseudocode, which is the basic, unoptimized version.

The Basic Implementation

Let's write the Java code for Bubble Sort based on the first pseudocode we created. This version will sort the array correctly, but it will complete all possible passes, even if the array becomes sorted earlier. It's a great starting point for understanding the core implementation.

Here is a complete, runnable Java class:

import java.util.Arrays;


public class BasicBubbleSort {


    // Method to perform bubble sort on an integer array
    void bubbleSort(int arr[]) {
        int n = arr.length;
        
        // Outer loop controls the number of passes
        for (int i = 0; i < n - 1; i++) {
            
            // Inner loop performs the comparisons and swaps
            for (int j = 0; j < n - i - 1; j++) {
                
                // Compare two adjacent elements
                if (arr[j] > arr[j+1]) {
                    // If they are in the wrong order, swap them
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }


    // A main method to test our implementation
    public static void main(String args[]) {
        BasicBubbleSort sorter = new BasicBubbleSort();
        int arr[] = {5, 1, 4, 2, 8};
        
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        
        sorter.bubbleSort(arr);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Code Breakdown: Translating the Blueprint

Let's connect this Java sorting algorithm code directly back to our pseudocode.

• void bubbleSort(int arr[]): This is our main sorting method. It takes an integer array arr as input and sorts it "in-place," meaning it modifies the original array directly.
• int n = arr.length;: Just like in the pseudocode, we first get the size of the array to control our loops.
• for (int i = 0; i < n - 1; i++): This is the outer loop that ensures we make enough passes to sort the entire array. The n - 1 is because in the worst-case scenario, n-1 passes are sufficient.
• for (int j = 0; j < n - i - 1; j++): This is the inner loop for the comparisons. The n - i - 1 logic is a small but important optimization. After each pass i, the last i elements are already in their final sorted positions, so we don't need to check them again. This makes our array sorting in Java slightly more efficient.

The Swap Logic:

if (arr[j] > arr[j+1]) {
    int temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
}

This is the classic way to swap two variables in most programming languages. We use a temporary variable (temp) to hold one value while we perform the exchange. This block is the heart of the sorting process.

Running the Example

When you run the main method, you will see the following output:

Unsorted array: [5, 1, 4, 2, 8]
Sorted array: [1, 2, 4, 5, 8]
This basic implementation perfectly demonstrates the core logic of Bubble Sort. In the next section, we will build upon this foundation to create the smarter, optimized version.

The Smart Upgrade: Optimized Bubble Sort

The basic implementation of Bubble Sort works, but it has a significant drawback: it's not very smart. It will dutifully complete every single pass, even if the array gets perfectly sorted after the very first one. This is inefficient. We can make a simple but powerful enhancement to create an optimized Bubble Sort in Java that stops as soon as the job is done.

This "smart upgrade" is based on a simple observation we made during our dry run: if a full pass is completed with zero swaps, it means the array is already in sorted order. There's no need to continue. We can add a mechanism to detect this and break out of the loop early.

Here is the efficient Bubble Sort Java code that implements this logic:

import java.util.Arrays;


public class OptimizedBubbleSort {


    // Method to perform the optimized bubble sort
    void bubbleSort(int arr[]) {
        int n = arr.length;
        boolean swapped; // A flag to track if a swap happened


        // Outer loop for the passes
        for (int i = 0; i < n - 1; i++) {
            // At the start of each new pass, assume no swaps will occur
            swapped = false; 
            
            // Inner loop for comparisons
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    // If a swap is needed, perform it
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    
                    // And set our flag to true
                    swapped = true; 
                }
            }


            // After the inner loop, check the flag.
            // If swapped is still false, the array is sorted.
            if (!swapped) {
                break; // Exit the main loop
            }
        }
    }


    // Main method to test the optimized implementation
    public static void main(String args[]) {
        OptimizedBubbleSort sorter = new OptimizedBubbleSort();
        // Let's test with a nearly sorted array
        int arr[] = {1, 2, 8, 4, 5}; 
        
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        
        sorter.bubbleSort(arr);
        
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Code Breakdown: The Optimization Secret

The magic lies in just a few extra lines of code, centered around the swapped boolean variable.

1. boolean swapped;: We declare a boolean flag. This variable will be our memory for each pass, telling us whether we had to move any elements.
2. swapped = false;: At the beginning of every outer loop iteration (each pass), we reset this flag to false. We go into each pass with the optimistic assumption that the array is sorted.
3. swapped = true;: If the if condition (arr[j] > arr[j+1]) is met and a swap occurs, we immediately set swapped to true. This tells us that the array was not yet fully sorted during this pass.
4. if (!swapped) { break; }: This is the crucial check. After the inner loop finishes a complete pass, we examine the swapped flag.
   • If it's true, it means we made at least one swap, so the array might still not be fully sorted. The outer loop continues to the next pass.
   • If it's false (which is what !swapped checks for), it's proof that we went through the entire array and every adjacent pair was already in the correct order. The array is sorted! The break; statement then terminates the outer loop immediately, saving us from redundant, useless passes.

This Java code optimization significantly improves the algorithm's best-case performance, making it a much more practical and intelligent sorting solution for nearly-sorted data.