bubbleSort(A, n): swapped = true while not swapped: swapped = false for i = 0 ... n - 2: if A[i] > A[i + 1]: swap A[i] and A[i + 1] swapped = true
We go through the input sequence looking for inversions. For each inversion, we swap the two elements to put them in order. This way, larger elements bubble up and smaller elements bubble down.
When we go through the input sequence without making a single swap (and find that the sequence doesn’t have any more inversions), we stop.
In the best case, bubble sort takes time.
In the worst case, time.