# 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


Full Repo

Relevant Files: