1. What is Bubble Sort?

Bubble Sort is a simple sorting algorithm used to arrange elements in ascending or descending order. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. The largest elements “bubble” to the top of the list (i.e., the end of the array) after each full pass through the array.

2. Characteristics of Bubble Sort

1. Comparison-Based:
   Bubble Sort compares each pair of adjacent elements and decides whether to swap them. This makes it a comparison-based sorting algorithm.
2. In-Place Algorithm:
   Bubble Sort does not require any additional memory beyond the input array. All sorting is done by modifying the input array itself through swaps.
3. Stable Sorting:
   It maintains the relative order of equal elements. This property is important when the elements have associated data that should be preserved.
4. Easy to Understand and Implement:
   Though inefficient for large datasets, its simplicity makes it ideal for learning sorting fundamentals.

3. How Bubble Sort Works (Step-by-Step)

Pass 0 (Initial):       5   1   4   2   8

Pass 1, Step 1:         1 ↔ 5   4   2   8   → swapped
Pass 1, Step 2:         1   4 ↔ 5   2   8   → swapped
Pass 1, Step 3:         1   4   2 ↔ 5   8   → swapped
Pass 1, Step 4:         1   4   2   5 < 8   → no swap
                       ------------------------
                       Sorted:             [8]

Pass 2, Step 1:         1 < 4   2   5   8   → no swap
Pass 2, Step 2:         1   2 ↔ 4   5   8   → swapped
Pass 2, Step 3:         1   2   4 < 5   8   → no swap
                       ------------------------
                       Sorted:         [5, 8]

Pass 3, Step 1:         1 < 2   4   5   8   → no swap
Pass 3, Step 2:         1   2 < 4   5   8   → no swap
                       ------------------------
                       Sorted:     [4, 5, 8]

Pass 4 (No swaps):      1   2   4   5   8   → already sorted
                       ------------------------
                       Sorted: [1, 2, 4, 5, 8]

4. Implementation

public class OptimizedBubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // If no elements were swapped, stop
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 1, 4, 2, 8};
        bubbleSort(data);

        System.out.println("Sorted array:");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

5. Time and Space Complexity

Case	Time Complexity	Explanation
Best Case	O(n)	Already sorted, early exit used
Average	O(n²)	Two nested loops
Worst Case	O(n²)	Reversed order
Space	O(1)	In-place sort

6. When to Use Bubble Sort

• For teaching purposes: demonstrates core sorting concepts.
• When the dataset is very small or nearly sorted.
• If stability is required (won’t reorder equal elements).

7. Limitations of Bubble Sort

1. Poor Performance on Large Data Sets:
   With a worst-case time complexity of O(n²), it’s significantly slower than more advanced algorithms like Merge Sort or Quick Sort.
2. Unnecessary Comparisons:
   Without optimization, it continues looping even when the array is already sorted.
3. Not Practical in Production:
   Due to inefficiency, it is not used in real-world applications involving large datasets.