Prerequisites (click to view)
graph LR
ALG(["fas:fatrophy Bubble Sort fas:fatrophy #160;"])
ASY_ANA(["fas:facheck Asymptotic Analysis #160;"])
click ASY_ANA "./mathasymptoticanalysis"
ARRAY(["fas:facheck Array #160;"])
click ARRAY "./listdatastructarray"
ASY_ANA>ALG
ARRAY>ALG
Bubble sort is an easy algorithm to implement; however, its runtime is quadratic ($O(n^2)$) so it’s not a particularly efficient algorithm. As the name implies, it starts at the beginning of the data and bubbles each element to its proper place. The animation below illustrates bubble sort on an integer array containing five items.
History
Bubble sort was originally referred to as “sorting by exchange”. It’s difficult to determine its exact origin because it was never regarded as an optimal choice for a general purpose sorting solution. The first mention of sorting by exchange is in a 1956 paper by Edward H. Fried entitled Sorting on Electronic Computer Systems^{1}. The paper offers up the algorithm as an example of an inefficient algorithm. Then, as today, its primary utility is pedagogical.
The paucity of prose here is intentional as it is not an effective tool for conveying algorithm details. The reader is encouraged to thoroughly peruse the pseudo code instead.
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 unsortedtoindex $\gets \vert A \vert  2$
\WHILE{sorted is false}
\STATE sorted $\gets$ true
\FOR{i $\gets$ 0 to unsortedtoindex}
\IF{$A_i \gt A_{i+1}$}
\STATE swap $A_i$ and $A_{i+1}$
\STATE sorted $\gets$ false
\ENDIF
\ENDFOR
\STATE usortedtoindex $\gets$ unsortedtoindex  1
\ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Asymptotic Complexity
$O(n^2)$
Source Code
Relevant Files:
Click here for build and run instructions
Exercises

Assume line 4 of the bubble sort pseudo code is changed to:
\(\text{for}\space j \in A \space\text{do}\)
Specify $\Omega$ for the modified algorithm.Answers (click to expand)
$\Omega(n^2)$  There is no chance for the algorithm to stop early so the lower bound is the same as the upper bound. The modified algorithm becomes $\Theta(n^2)$.

Specify $\Omega$ for the bubble sort pseudo code algorithm.
HINT: What happens in the case where the data is already in sorted order.
Answers (click to expand)
$\Omega(n)$  If the data is already sorted, line 9 will never set the
sorted
variable to false. As such, line 4 will evaluate to false after iterating through the array once.  Using the programming language of your choice, implement a bubble sort
function that accepts:
 an array of any type
 a sorting strategy
Answers (click to expand)
See the C implementation provided in the links below. Your implementation may vary significantly and still be correct.
 bubble_sort.h
 bubble_sort.c
 bubble_sort_test.c  The
sort.txt
file contains one integer per line. Using the programming language of your
choice, write a program that parses the file and places all the integers in
an array. Next, using bubble sort, sort the array in the following order:
 odd numbers in ascending order
 even number is ascending order
For instance, the numbers 3, 4, 8, 6, 9, 1 sort to 1, 3, 9, 4, 6, 8.
Answers (click to expand)
See the C implementation provided in bubble_sort_test.c Your implementation may vary significantly and still be correct.
For reference, the first 10 sorted numbers are 1, 3, 5, 7, 9, 11, 13, 15, 17, and 19. The last 10 sorted numbers are 9982, 9984, 9986, 9988, 9990, 9992, 9994, 9996, 9998, and 10000.

Available online at https://dl.acm.org/doi/10.1145/320831.320833 ↩