Bubble sort is a sorting algorithm that repeatedly compares adjacent elements and exchanges them when they are out of order. After one complete
pass through a list of 
elements, an element of maximum value has moved to its final position. Repeating
the process on the remaining prefix sorts the list.
Bubble sort uses 
comparisons and exchanges in the average and worst cases. In big-O
notation, this means that the number of operations is bounded by a constant multiple
of 
for all sufficiently large 
. With a test that stops after a pass containing no exchanges,
its best-case running time on an already sorted list is 
.
