Bubble Sort

Bubble sort is the easiest to implement but is typically a poor performer when the values in the input array are randomly sorted. At the extremes, bubble sort performs better than all other sorting algorithms when the input is pre-sorted and worst than all others when the input is reverse sorted.

Asymptotic Complexity

$O(n^2)$

Pseudo Code

sort:
    // side effect: rearranges the values in A
    A = input array
    
    unsorted_to = num items in A - 1
    sorted = false
    
    while sort is false:
        sorted = true

        for i = 0 to unsorted_to:
            if (A[i] > A[i + 1]:
                swap A[i] and A[i+1]
                sorted = false

         usorted_to -= 1

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions