Bubble Sort

Question (LC.463)

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n^2) algorithm.

Key Idea

Each iteration the largest element will be bubbled to the top.

Code

public void bubbleSort(int[] arr) {
    // each outer loop guarantees the largest element 
    // is bubbled to the right place
    for (int i = 0; i < arr.length - 1; i++)
        for (int j = 1; j < arr.length - i; j++)
            if (arr[j-1] > arr[j]) swap(arr, j-1, j);
}

private void swap(int[] arr, int index1, int index2) {
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

Time & Space Complexity

Bubble sort has quite a few nice properties. Since it only involves swapping elements, it is in-place. The finishing order is also stable. The time complexity can be calculated with a simple summation $\sum\limits_{i=0}^{n-1} i = n^2$.

Optimization

We can add a flag to check if the inner loop has 0 swaps. That will improve the best case to O(n).