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

\begin{algorithm}
\caption{Bubble Sort}
\begin{algorithmic}
\REQUIRE $A$ = list of numbers where $\vert A \vert \gt 2$
\ENSURE $A$ sorted in sequential order
\FUNCTION{bubbleSort}{$A$}
    \STATE sorted $\gets$ false
    \STATE unsorted-to-index $\gets \vert A \vert - 2$
    \WHILE{sorted is false}
        \STATE sorted $\gets$ true
        \FOR{i $\gets$ 0 to unsorted-to-index}
            \IF{$A_i \gt A_{i+1}$}
                \STATE swap $A_i$ and $A_{i+1}$
                \STATE sorted $\gets$ false
            \ENDIF
        \ENDFOR
        \STATE usorted-to-index $\gets$ unsorted-to-index - 1
    \ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
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