Bubble Sort Algorithm: Principle and Java Implementation¶

Sorting is a fundamental and common task in programming. Bubble Sort is one of the simplest sorting algorithms, whose core idea is to repeatedly compare adjacent elements and swap their positions, allowing larger elements to “bubble up” to the end of the array (for ascending order) or smaller elements to “bubble up” to the beginning (for descending order).

Step-by-Step Explanation of Sorting¶

Using the array [5, 2, 9, 1, 5] as an example, let’s demonstrate the ascending sorting process:

1. First Pass (Unsorted portion: [5, 2, 9, 1, 5])
   - Compare 5 and 2: 5 > 2, swap → [2, 5, 9, 1, 5]
   - Compare 5 and 9: 5 < 9, no swap
   - Compare 9 and 1: 9 > 1, swap → [2, 5, 1, 9, 5]
   - Compare 9 and 5: 9 > 5, swap → [2, 5, 1, 5, 9]
   - Result: The largest element 9 has “bubbled up” to the end; the unsorted portion becomes [2, 5, 1, 5]

2. Second Pass (Unsorted portion: [2, 5, 1, 5])
   - Compare 2 and 5: 2 < 5, no swap
   - Compare 5 and 1: 5 > 1, swap → [2, 1, 5, 5]
   - Compare 5 and 5: 5 = 5, no swap
   - Result: The second largest element 5 has “bubbled up” to the second last position; the unsorted portion becomes [2, 1, 5]

3. Third Pass (Unsorted portion: [2, 1, 5])
   - Compare 2 and 1: 2 > 1, swap → [1, 2, 5]
   - Compare 2 and 5: 2 < 5, no swap
   - Result: The third largest element 5 has “bubbled up” to the third last position; the unsorted portion becomes [1, 2]

4. Fourth Pass (Unsorted portion: [1, 2])
   - Compare 1 and 2: 1 < 2, no swap
   - Result: Sorting completed; the array becomes [1, 2, 5, 5, 9]

Java Code Implementation¶

public class BubbleSort {
    /**
     * Implementation of the Bubble Sort algorithm (ascending order)
     * @param arr Array to be sorted
     */
    public static void bubbleSort(int[] arr) {
        // Outer loop: Controls the number of passes (at most n-1 passes)
        for (int i = 0; i < arr.length - 1; i++) {
            boolean swapped = false; // Optimization flag: Did any swap occur in this pass?
            // Inner loop: Controls comparisons per pass (sorted elements are no longer compared)
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // If current element > next element, swap positions
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];       // Temporary variable to store current element
                    arr[j] = arr[j + 1];     // Swap next element to current position
                    arr[j + 1] = temp;       // Swap current element to next position
                    swapped = true;          // Mark that a swap occurred in this pass
                }
            }
            // If no swaps in this pass, the array is already sorted; exit early
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        // Test array
        int[] arr = {5, 2, 9, 1, 5};
        System.out.println("Before sorting: " + java.util.Arrays.toString(arr));

        // Call bubble sort
        bubbleSort(arr);

        System.out.println("After sorting: " + java.util.Arrays.toString(arr));
    }
}

Key Code Explanations¶

1. Outer Loop: Controls the number of passes. For an array of length n, at most n-1 passes are needed (the last element is already sorted).
2. Inner Loop: Compares adjacent elements. The number of comparisons decreases by i each pass (since i elements are already sorted).
3. Swap Logic: Uses a temporary variable temp to swap adjacent elements, ensuring stable sorting.
4. Optimization: The swapped flag terminates the algorithm early if no swaps occur in a pass (ideal for nearly sorted arrays).

Time and Space Complexity¶

• Time Complexity:
• Worst case (completely reversed): O(n²) (all passes and comparisons are performed).
• Average case: O(n²).
• Best case (already sorted): O(n) (optimized with the swapped flag to exit early).
• Space Complexity: O(1) (only temporary variables are used; in-place sorting).

Conclusion¶

Bubble Sort is simple and intuitive, making it suitable for beginners to understand core sorting concepts. However, due to its high time complexity (O(n²)), it is rarely used for large datasets. It is typically taught or applied to small-scale sorting scenarios. After mastering Bubble Sort, one can further explore more efficient algorithms like Quick Sort or Merge Sort.