Bubble Sort

Definition

A simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, "bubbling" larger elements to the end.

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

Basic Bubble Sort

// Time: O(n²) always
public void bubbleSort(int[] arr) {
    int n = arr.length;

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

Optimized Bubble Sort

// Time: O(n) best case (already sorted)
public void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    boolean swapped;

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

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

        // If no swaps, array is sorted
        if (!swapped) break;
    }
}

Further Optimized (Track Last Swap)

// Reduces comparisons by tracking last swap position
public void bubbleSortFurther(int[] arr) {
    int n = arr.length;
    int newN;

    while (n > 1) {
        newN = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                newN = i;  // Last swap position
            }
        }
        n = newN;  // Elements after newN are sorted
    }
}

Recursive Bubble Sort

public void bubbleSortRecursive(int[] arr, int n) {
    if (n == 1) return;  // Base case

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

    if (!swapped) return;  // Already sorted

    bubbleSortRecursive(arr, n - 1);
}

---

Variations

Descending Order

public void bubbleSortDescending(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {  // Changed comparison
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Cocktail Shaker Sort (Bidirectional Bubble Sort)

// Sorts in both directions alternately
// Better for "turtle" elements (small values at end)
public void cocktailSort(int[] arr) {
    boolean swapped = true;
    int start = 0;
    int end = arr.length - 1;

    while (swapped) {
        swapped = false;

        // Forward pass (bubble up)
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        end--;

        if (!swapped) break;

        swapped = false;

        // Backward pass (bubble down)
        for (int i = end; i > start; i--) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                swapped = true;
            }
        }
        start++;
    }
}

Generic Bubble Sort

public <T extends Comparable<T>> void bubbleSort(T[] arr) {
    int n = arr.length;
    boolean swapped;

    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j].compareTo(arr[j + 1]) > 0) {
                T temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

---

Step-by-Step Example

---

Common Interview Questions

Detect Sorted Array

public boolean isSorted(int[] arr) {
    // One pass of bubble sort with no swaps = sorted
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

Count Swaps

public int countSwaps(int[] arr) {
    int n = arr.length;
    int swaps = 0;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swaps++;
            }
        }
    }
    return swaps;
}
// For reverse sorted array of n elements: n(n-1)/2 swaps

---

Tips & Tricks

---