0

Bubble Sort

Easy

Walk the array swapping any pair that is out of order. After pass k the k largest values have bubbled to the end.

comparison sortstablein place
TimeO(n^2), best O(n) when already sorted
SpaceO(1)
InputComma separated numbers
5
0
1
1
4
2
2
3
8
4
0
5
2
6

Starting array. Nothing is known to be in place yet.

comparisons0swaps0
1 / 48
for i from 0 to n-1:
swapped = false
for j from 0 to n-i-2:
if a[j] > a[j+1]:
swap(a[j], a[j+1]); swapped = true
if not swapped: break
Why it matters

Stable. Almost never the right answer, but the clearest place to see invariants.

Practise this
Sort ColorsMSort an ArrayM
Keyboard
space play← → stepr restartctrl K search

More in Sorting

Quickselect
O(n) expected, O(n^2) worst
Selection Sort
O(n^2) always
Insertion Sort
O(n^2), O(n) on nearly sorted input
Merge Sort
O(n log n) always
Quick Sort
O(n log n) average, O(n^2) worst
Counting Sort
O(n + k)
Next visualiser
Selection Sort