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 = trueBubble Sort
-
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.
Example
Pseudocode
Complexity
-
In the best case, bubble sort takes time.
-
In the worst case, time.