Bubble Sort
The idea
Imagine kids lining up by height, but each kid can only compare with the neighbour directly beside them and swap places. After one full walk down the line, the tallest kid has "bubbled" all the way to the back. Every extra walk bubbles the next-tallest into place.
The problem
You have a row of numbers in random order and you want them arranged from smallest to largest. Bubble sort is the most natural first idea: walk along the row, and whenever two neighbours are in the wrong order, swap them. Repeat until nothing needs swapping.
Why it's slow
Bubble sort compares every neighbour pair, pass after pass. For 5 numbers that is 10 comparisons. For 8 numbers, 28. For 100 numbers, 4,950. Double the list and the work roughly quadruples — that growth pattern is called O(n²). It feels fine on this screen and becomes hopeless on real data. Try the worst case yourself: enter a reversed list like 9,8,7,6,5 in the player and watch the swap counter.
Pseudocode
-
repeat for each pass
Explain this line
Each pass bubbles the biggest remaining value to the end.
-
for each pair position j in the unsorted part
Explain this line
j walks the unsorted part of the array, one neighbour pair at a time.
-
compare a[j] and a[j+1]
Explain this line
Bubble sort only ever compares neighbours — that is its whole trick.
-
swap them if a[j] > a[j+1]
Explain this line
The bigger value moves one slot to the right.
-
lock the last position of this pass as sorted
Explain this line
The sorted tail at the end grows by one each pass, so each pass is shorter.
Complexity
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
This basic version always does every comparison. A common tweak — stop when a pass makes no swaps — improves the best case (already sorted input) to O(n). Space is O(1): it sorts in place.
Code
python
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return ajava
void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}cpp
void bubbleSort(std::vector<int>& a) {
for (size_t i = 0; i + 1 < a.size(); ++i) {
for (size_t j = 0; j + 1 < a.size() - i; ++j) {
if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
}
}
}javascript
function bubbleSort(a) {
for (let i = 0; i < a.length - 1; i++) {
for (let j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
}
}
return a;
}dart
void bubbleSort(List<int> a) {
for (var i = 0; i < a.length - 1; i++) {
for (var j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
final t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}