The Blueprint (Pseudocode)

Before we jump into writing actual Java code, it's a best practice to first outline the logic in a simplified, human-readable format. This is where pseudocode comes in. It acts as a blueprint or a sketch of the algorithm, allowing us to focus purely on the logic without worrying about the specific syntax of a programming language. Let's create the Bubble Sort pseudocode to solidify our understanding.

The Basic Bubble Sort Algorithm

This is the most straightforward implementation, directly translating the logic of nested passes.

Algorithm: Bubble Sort

Procedure bubbleSort(array)
    n = length(array)
    
    // Outer loop for the number of passes
    for i from 0 to n - 1
        
        // Inner loop for comparisons in each pass
        for j from 0 to n - i - 2
            
            // Compare adjacent elements
            if array[j] > array[j + 1] then
                
                // Swap them if they are in the wrong order
                swap(array[j], array[j + 1])
            end if
            
        end for
        
    end for
End Procedure

Breaking Down the Blueprint:

• procedure bubbleSort(array): This defines our function, which takes an array as input.
• n = length(array): We get the total number of elements in the array.
• for i from 0 to n-1: This is the outer loop. It controls the number of passes. An array of n elements will need at most n-1 passes to be fully sorted.
• for j from 0 to n-i-2: This is the inner loop. It handles the actual comparisons. The n-i-1 part is clever: it ensures the inner loop doesn't check the elements that are already sorted and placed at the end of the array from previous passes.
• if array[j] > array[j+1]: This is the core comparison logic.
• swap(...): If the condition is true, the two elements exchange places.

The Optimized Bubble Sort Algorithm (The Smarter Blueprint)

As we saw in the dry run, the basic algorithm will keep running even if the array gets sorted early. The optimized algorithm fixes this inefficiency.

Procedure optimizedBubbleSort(array)
    n = length(array)
    
    // Outer loop for the number of passes
    for i from 0 to n - 1
        
        // A flag to check if any swap happened in a pass
        swapped = false
        
        // Inner loop for comparisons
        for j from 0 to n - i - 2
            
            // Compare adjacent elements
            if array[j] > array[j + 1] then
                
                // Swap them
                swap(array[j], array[j + 1])
                
                // Set the flag to true
                swapped = true
            end if
            
        end for
        
        // If no swaps happened in this pass, the array is sorted
        if swapped == false then
            break   // Exit the outer loop early
        end if
        
    end for
End Procedure

What's the Upgrade?

The key improvement is the swapped boolean flag.

1. Initialize swapped = false: At the start of each pass (the outer loop), we assume no swaps will occur.
2. Set swapped = true: If a swap does happen inside the inner loop, we set the flag to true.
3. Check the Flag: After the inner loop completes, we check the flag. If it's still false, it means the entire pass was completed without a single swap. This is our signal that the array is perfectly sorted, and we can break out of the main loop, saving valuable processing time.

This algorithm logic blueprint is the final step before implementation. With this pseudocode in hand, translating the Bubble Sort algorithm into Java or any other programming language becomes much more intuitive.