Algorithm Overview

Bubble sort is a foundational comparison-based sorting technique. It operates by iterating through a list, examining adjacent elements, and swapping them if they are in the incorrect order. This process causes the larger values to gradually "bubble" to the end of the array with each complete pass. The algorithm continues this traversal until no more swaps are required, indicating that the collection is fully sorted.

Basic Implementation

The following Java example illustrates the standard unoptimized version. An outer loop controls the iterations, while an inner loop handles the pairwise comparisons. The range of the inner loop shortens with each outer iteration because the final elements of the array become progressively sorted.

public class Sorter {
    public static void bubbleSort(int[] data) {
        int size = data.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                // Compare adjacent elements
                if (data[j] > data[j + 1]) {
                    // Swap if the element found is greater than the next element
                    int buffer = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = buffer;
                }
            }
        }
    }
}

Performance Optimization

A significant inefficiency in the basic implementation is that it continues iterating even after the array is sorted. To resolve this, we can introduce a boolean flag to track whether any swaps occurred during a pass. If a full pass completes without triggering a swap, the algorithm terminates immediately, saving processing time.

public static void optimizedBubbleSort(int[] data) {
    int size = data.length;
    boolean hasSwapped;
    for (int i = 0; i < size - 1; i++) {
        hasSwapped = false;
        for (int j = 0; j < size - i - 1; j++) {
            if (data[j] > data[j + 1]) {
                int buffer = data[j];
                data[j] = data[j + 1];
                data[j + 1] = buffer;
                hasSwapped = true;
            }
        }
        // If no two elements were swapped by inner loop, then break
        if (!hasSwapped) {
            break;
        }
    }
}

Time Complexity Analysis

In terms of efficiency, bubble sort has a quadratic time complexity of O(n²) in both the average and worst-case scenarios. However, when implemented with the optimization flag described above, the best-case time complexity (when the input is already sorted) improves to linear time, or O(n).