15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Bubble sort compares neighboring values and swaps them when the left one is larger. One left-to-right pass carries the largest unsorted value to the right end, so the unsorted part shrinks by one each pass. It takes O(n^2) time in the worst case, O(n) on sorted input with an early exit, and O(1) extra space.
| Worst case time | O(n^2), n(n-1)/2 comparisons |
|---|---|
| Best case time | O(n), one pass with no swaps on sorted input |
| Extra space | O(1), sorts in place |
| Stable | Yes, because it swaps only when left > right |
| Passes | At most n - 1; stops at the first pass with no swaps |
Bubble Sort works on an array that must end in nondecreasing order.
Before using it, be comfortable with these sorting requirements:
Bubble Sort compares neighboring positions. When the left value is greater than the right value, it swaps them.
We will sort in ascending order. The swap test is strictly:
left value > right value
If two keys are equal, the algorithm does not swap them.
Reference for elementary sorting properties and traces: Elementary Sorts.
Use this array throughout the lesson:
1index: 0 1 2 3
2value: [4, 1, 3, 2]Start at index 0 and compare adjacent values.
0 with index 1.1 with index 2.2 with index 3.Each comparison may swap the pair. A large value can move right one position at a time. After one complete left-to-right pass, the largest value still in the unsorted part reaches the right end.
For this input, 4 reaches index 3 during the first pass.
The unsorted boundary initially ends at index 3. Positions to the right of that boundary, if any, are already fixed and will not be compared again.
Bubble Sort on [4, 1, 3, 2]: each pass compares neighbours left to right, swapping when left > right, and fixes the largest value at the right end. Pass 3 makes zero swaps, so it stops.
Compare indices 0 and 1.
14 > 1, so swap.
2
3[4, 1, 3, 2] -> [1, 4, 3, 2]Move one position right. Compare indices 1 and 2.
14 > 3, so swap.
2
3[1, 4, 3, 2] -> [1, 3, 4, 2]Move right again. Compare indices 2 and 3.
14 > 2, so swap.
2
3[1, 3, 4, 2] -> [1, 3, 2, 4]The first pass is complete.
1index: 0 1 2 | 3
2value: [1, 3, 2 | 4]The suffix [4] is fixed. No later pass needs to inspect index 3.
Compare only indices before the fixed suffix.
Start with:
1index: 0 1 2 | 3
2value: [1, 3, 2 | 4]Compare indices 0 and 1.
11 > 3 is false, so do not swap.
2
3[1, 3, 2, 4] -> [1, 3, 2, 4]Compare indices 1 and 2.
13 > 2, so swap.
2
3[1, 3, 2, 4] -> [1, 2, 3, 4]The second pass is complete.
The suffix [3, 4] is fixed.
Only one adjacent comparison remains.
Compare indices 0 and 1.
11 > 2 is false, so do not swap.
2
3[1, 2, 3, 4] -> [1, 2, 3, 4]The pass made zero swaps. Stop immediately.
The final array is:
1[1, 2, 3, 4]After the first pass, we saw that 4 reached the final position.
After the second pass, 3 and 4 occupied the final two positions.
The same fact continues after every completed pass:
After
kcompleted full passes, the lastkpositions contain theklargest input elements in nondecreasing order and will not change.
The statement is the loop invariant.
For our example:
1After 1 completed pass: [1, 3, 2 | 4]
2 fixed suffix
3
4After 2 completed passes: [1, 2 | 3, 4]
5 fixed suffixDuring a pass, each adjacent comparison moves the larger member of the pair rightward. By the end of a pass, no value in the current unsorted prefix is larger than the value placed at its rightmost position. That position is final.
The trace gives the algorithm step by step.
boundary be the last index that still belongs to the unsorted prefix.0.array[j] and array[j + 1].array[j] > array[j + 1], swap them and record that a swap happened.boundary by one. Its old position now belongs to the fixed suffix.The comparison limit prevents an out-of-bounds read. If boundary is 3, the final left index we may use is 2, because the algorithm reads array[j + 1].
A pass that finds no swaps means:
1array[0] <= array[1]
2array[1] <= array[2]
3array[2] <= array[3]The whole array is already in nondecreasing order.
Input: array, a mutable array of comparable values.
Return value: The same array reference, after sorting it in nondecreasing order.
Mutation behavior: Rearranges values directly inside array.
Boundary behavior: Arrays of length 0 or 1 perform no comparisons.
Helper contract: swap(array, a, b) exchanges the values at valid indices a and b using one temporary value.
101 procedure bubbleSort(array):
202 n <- length(array)
303
404 for boundary <- n - 1 down to 1:
505 swapped <- false
606
707 for j <- 0 to boundary - 1:
808 if array[j] > array[j + 1]:
909 swap(array, j, j + 1)
1010 swapped <- true
1111
1212 if swapped = false:
1313 return array
1414
1515 return arrayThe inner loop ends at boundary - 1, rather than at boundary.
When j = boundary - 1, the comparison is:
1array[boundary - 1] and array[boundary]Both indices are valid, and the comparison reaches the rightmost position of the current unsorted prefix.
Trace bubbleSort([4, 1, 3, 2]).
101 bubbleSort(array)
202 n <- 4The outer loop on line 04 begins with boundary = 3.
boundary = 3105 swapped <- falseInner loop line 07 uses j = 0, 1, 2.
107 j <- 0
208 array[0] > array[1] means 4 > 1, true
309 swap(array, 0, 1)
4 array becomes [1, 4, 3, 2]
510 swapped <- true107 j <- 1
208 array[1] > array[2] means 4 > 3, true
309 swap(array, 1, 2)
4 array becomes [1, 3, 4, 2]
510 swapped <- true107 j <- 2
208 array[2] > array[3] means 4 > 2, true
309 swap(array, 2, 3)
4 array becomes [1, 3, 2, 4]
510 swapped <- true112 swapped = false is falseDo not return. The outer loop continues with boundary = 2.
boundary = 2105 swapped <- falseInner loop line 07 uses j = 0, 1.
107 j <- 0
208 array[0] > array[1] means 1 > 3, false
3 Lines 09 and 10 do not run.
4 array remains [1, 3, 2, 4]107 j <- 1
208 array[1] > array[2] means 3 > 2, true
309 swap(array, 1, 2)
4 array becomes [1, 2, 3, 4]
510 swapped <- true112 swapped = false is falseDo not return. The outer loop continues with boundary = 1.
boundary = 1105 swapped <- falseInner loop line 07 uses only j = 0.
107 j <- 0
208 array[0] > array[1] means 1 > 2, false
3 Lines 09 and 10 do not run.
4 array remains [1, 2, 3, 4]112 swapped = false is true
213 return arrayThe procedure returns:
1[1, 2, 3, 4]We need to show that the returned array is sorted and still contains the input values.
Consider one pass over positions 0 through boundary.
At each comparison, the larger of the two compared values ends up on the right:
1if left > right: swap
2otherwise: leave themA value that is larger than its right neighbor moves right by one position. As the scan continues, the maximum value in the unsorted prefix cannot be left behind by a smaller value. By the end of the pass, a maximum of that prefix is at index boundary.
Therefore, that maximum is in its final rightmost position.
Before any passes, the fixed suffix has length 0.
An empty suffix trivially contains the 0 largest input elements and is already sorted. The invariant holds before the first pass.
Assume that after k completed passes, the last k positions are fixed, sorted, and contain the k largest input elements.
The next pass only examines the prefix before that suffix. It does not touch any fixed suffix position.
As shown above, the pass moves a maximum of the remaining unsorted prefix to its rightmost position. That position is immediately before the old fixed suffix.
The fixed suffix now has length k + 1. It remains in nondecreasing order because the newly fixed value is no greater than any of the values already in the suffix.
The invariant is preserved.
If the outer loop finishes normally, every position belongs to the fixed suffix. By the invariant, the entire array contains all input elements in nondecreasing order.
Swapping only exchanges two array values. It neither creates nor removes values, so the output preserves the input values.
If swapped remains false, every adjacent comparison in that pass satisfied:
1array[j] <= array[j + 1]for every adjacent pair in the unsorted prefix.
The fixed suffix was already sorted, and the last value in the prefix is no greater than the first value in the suffix because the suffix contains the largest values. Therefore the entire array is in nondecreasing order.
Returning after a no-swap pass is valid.
The algorithm swaps only when:
1array[j] > array[j + 1]Equal keys are not swapped. Therefore, two equal adjacent records do not reverse their relative order. For example:
1[(2,A), (2,B)]remains:
1[(2,A), (2,B)]Let n be the array length.
Without early termination, the first pass compares n - 1 pairs.
The next pass compares n - 2 pairs because one suffix position is fixed.
The number of comparisons decreases to one:
1(n - 1) + (n - 2) + ... + 1The sum is:
1n(n - 1) / 2So the worst-case running time is O(n^2).
For example, [3, 2, 1] swaps on every compared inversion in the standard trace, and it still performs the full sequence of passes.
With the swapped flag, an already sorted array such as [1, 2, 3] makes one pass:
1n - 1 comparisonsIt finds no swap and stops. The best-case running time is O(n).
The algorithm uses:
swapped flag,These use constant space beyond the input array, so auxiliary space is O(1).
Incorrect assumption: One left-to-right pass sorts the entire array.
1for j <- 0 to n - 2:
2 if array[j] > array[j + 1]:
3 swap(array, j, j + 1)
4return arraySmallest exposing input:
1[3, 2, 1]Wrong trace:
1[3, 2, 1]
2compare 3 and 2 -> [2, 3, 1]
3compare 3 and 1 -> [2, 1, 3]The result is [2, 1, 3], which is unsorted.
Correction: Repeat passes over the shrinking unsorted prefix.
Incorrect inner-loop bound:
1for j <- 0 to boundary:
2 compare array[j] and array[j + 1]Smallest exposing input:
1[2, 1]With boundary = 1, the loop reaches j = 1 and attempts to read:
1array[2]That index is outside the array.
Correction: Stop at boundary - 1.
1for j <- 0 to boundary - 1:Incorrect condition:
1if array[j] >= array[j + 1]:
2 swap(array, j, j + 1)Smallest exposing input:
1[(2,A), (2,B)]Wrong result:
1[(2,B), (2,A)]The equal records reversed order.
Correction: Swap only for a strict inversion.
1if array[j] > array[j + 1]:1[] -> no comparisons; return []
2[5] -> no comparisons; return [5]
3[1,2,3] -> one no-swap pass; return [1,2,3]
4[3,2,1] -> swaps occur at every compared inversion in the standard traceImplement ascending Bubble Sort with this contract:
Executable tests verify:
1
2def bubble_sort(a):
3 comparisons = 0
4 for boundary in range(len(a) - 1, 0, -1):
5 swapped = False
6 for j in range(boundary): # stop at boundary - 1 so a[j + 1] is valid
7 comparisons += 1
8 if a[j] > a[j + 1]: # strict, so equal keys never swap
9 a[j], a[j + 1] = a[j + 1], a[j]
10 swapped = True
11 if not swapped: # a pass with no swaps means sorted
12 break
13 return comparisons
14
15nums = [4, 1, 3, 2]
16count = bubble_sort(nums)
17print(nums)
18print("comparisons:", count)
19print("sorted input comparisons:", bubble_sort([1, 2, 3]))1
2import java.util.Arrays;
3
4public class Main {
5 static int bubbleSort(int[] a) {
6 int comparisons = 0;
7 for (int boundary = a.length - 1; boundary >= 1; boundary--) {
8 boolean swapped = false;
9 for (int j = 0; j < boundary; j++) { // stop at boundary - 1 so a[j + 1] is valid
10 comparisons++;
11 if (a[j] > a[j + 1]) { // strict, so equal keys never swap
12 int tmp = a[j];
13 a[j] = a[j + 1];
14 a[j + 1] = tmp;
15 swapped = true;
16 }
17 }
18 if (!swapped) break; // a pass with no swaps means sorted
19 }
20 return comparisons;
21 }
22
23 public static void main(String[] args) {
24 int[] nums = {4, 1, 3, 2};
25 int count = bubbleSort(nums);
26 System.out.println(Arrays.toString(nums));
27 System.out.println("comparisons: " + count);
28 System.out.println("sorted input comparisons: " + bubbleSort(new int[]{1, 2, 3}));
29 }
30}1
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7int bubbleSort(vector<int>& a) {
8 int comparisons = 0;
9 for (int boundary = (int)a.size() - 1; boundary >= 1; boundary--) {
10 bool swapped = false;
11 for (int j = 0; j < boundary; j++) { // stop at boundary - 1 so a[j + 1] is valid
12 comparisons++;
13 if (a[j] > a[j + 1]) { // strict, so equal keys never swap
14 swap(a[j], a[j + 1]);
15 swapped = true;
16 }
17 }
18 if (!swapped) break; // a pass with no swaps means sorted
19 }
20 return comparisons;
21}
22
23int main() {
24 vector<int> nums = {4, 1, 3, 2};
25 int count = bubbleSort(nums);
26 cout << "[";
27 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
28 cout << "]" << endl;
29 cout << "comparisons: " << count << endl;
30 vector<int> sorted = {1, 2, 3};
31 cout << "sorted input comparisons: " << bubbleSort(sorted) << endl;
32}1
2function bubbleSort(a) {
3 let comparisons = 0;
4 for (let boundary = a.length - 1; boundary >= 1; boundary--) {
5 let swapped = false;
6 for (let j = 0; j < boundary; j++) { // stop at boundary - 1 so a[j + 1] is valid
7 comparisons++;
8 if (a[j] > a[j + 1]) { // strict, so equal keys never swap
9 [a[j], a[j + 1]] = [a[j + 1], a[j]];
10 swapped = true;
11 }
12 }
13 if (!swapped) break; // a pass with no swaps means sorted
14 }
15 return comparisons;
16}
17
18const nums = [4, 1, 3, 2];
19const count = bubbleSort(nums);
20console.log(`[${nums.join(', ')}]`);
21console.log(`comparisons: ${count}`);
22console.log(`sorted input comparisons: ${bubbleSort([1, 2, 3])}`);Line up people by height and let each neighbor pair swap places when the left person is taller. After one sweep the tallest person stands at the end of the row. Each later sweep fixes the next tallest.
Mostly to learn sorting. The invariant is easy to see: after k passes the last k positions are final. In practice insertion sort does the same job with fewer writes, and library sorts use faster algorithms.
It is correct and stable, but O(n^2) makes it slow on large inputs. Treat it as a teaching tool and an interview warm-up, not as something to ship.
At most n - 1. With the swapped flag it stops after the first pass that makes no swaps. [4, 1, 3, 2] needs three passes: the third finds nothing to swap.
Bubble sort swaps adjacent pairs and can finish in O(n) on sorted input. Selection sort scans for the minimum, makes at most n - 1 swaps, and always does n(n-1)/2 comparisons. Bubble sort is stable; basic selection sort is not.
Each step reads a[j + 1]. At j = boundary the code would read one cell past the unsorted part. On [2, 1] that is index 2, which is outside the array.