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.

Debug

Why this implementation is wrong? hint: what do you know for sure after each iteration in the outer loop?

def sortIntegers(self, A: List[int]) -> None:
    """
    Bubbling up the current element to the end of the list is also an option.
    """
    
    n = len(A)
    for i in range(n):
        for j in range(i, n-1):
            if A[j] > A[j+1]:
                temp = A[j]
                A[j] = A[j+1]
                A[j+1] = temp

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;
}

func sortIntegers (A *[]int)  {    
    arr := *A
    
    if arr == nil || len(arr) == 0 {
        return
    }
    
    // for each element swap the smallest value to the front 
    
    for i := 0; i < len(arr); i++ {
        for j := i; j > 0; j-- {
            if arr[j-1] > arr[j] {
                swap(A, j-1, j)
            }
        }
    }
}

func swap (A *[]int, i, j int) {
    arr := *A 
    temp := arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

def bubbleSort(A: List[int]) -> None:
    """
    Bubbling the largest element to the end of the list 
    """
    
    n = len(A)
    for i in range(n):
        for j in range(n-i-1):
            if A[j] > A[j+1]:
                swap(A, j, j+1)


def swap(A: List[Any], i: int, j: int) -> None:
    temp = A[i]
    A[i] = A[j]
    A[j] = 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).