Concept Overview

Bubble Sort is another simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process "bubbles up" the largest (or smallest) element to the end of the array in each iteration.

How It Works

• Iterate through the array from the start to the end.
• For each pair of adjacent elements, swap them if they are out of order.
• After each iteration, the largest element in the unsorted portion is placed at the end.
• Repeat until no more swaps are needed, indicating the array is sorted.

Time and Space Complexity

• Time Complexity:
  • Best Case: O(n) (array is already sorted, with an optimization to check for swaps)
  • Average Case: O(n²)
  • Worst Case: O(n²) (array is reverse sorted)
• Space Complexity: O(1) (in-place sorting)

Why Use Bubble Sort?

• Purpose: Bubble Sort is primarily used for educational purposes due to its simplicity and intuitive nature.
• Relevance: It can be useful in scenarios where the array is nearly sorted, as the optimized version exits early if no swaps occur.
• Limitations: Like Selection Sort, its quadratic complexity makes it impractical for large datasets.

Java Implementation

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // Last i elements are already in place
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap adjacent elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no swapping occurred, array is sorted
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Best Practices and Pitfalls

• Best Practice: Include the swapped flag optimization to exit early if the array is already sorted.
• Pitfall: Bubble Sort is sensitive to the initial order of elements. A reverse-sorted array requires the maximum number of comparisons and swaps.