Description

Bubble sort goes through an entire array and compares each neighboring number. It then swaps the numbers and keeps doing so until the list is in order.

Algorithm

int [] bubbleSort (int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = 1; j < nums.length; j++) {
            if (nums[j-1] > nums[j]) {
                swap[j, j-1];
            }
        }
    }
    return nums;
}

Characteristics

Time

• Best: Already sorted O(n) - must keep track of sweeps
• Avg/Worst: O(n^2) - n pass n swaps, it can be shown that if input is random O(n^2/2)

Space

• O(1), bubble sort is an in place algorithm and only needs the input array.