Bubble Sort
Last updated
Bubble sort repeatedly steps through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. After each full pass the largest remaining value has "bubbled" to its correct position at the end, so each pass looks at one fewer element. Press play above to watch the comparisons and swaps, or step through them one at a time.
It is one of the simplest sorting algorithms to understand, which makes it a great first algorithm - but its O(n²) running time makes it impractical for large inputs.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(n) | Already sorted, with an early-exit check |
| Average case | O(n²) | Random order |
| Worst case | O(n²) | Reverse-sorted |
| Space | O(1) | In-place, only a temp variable |
| Stable | Yes | Equal elements keep their relative order |
Step by step
| Step | What happens |
|---|---|
| 1 | Start at the beginning of the array. |
| 2 | Compare the current element with the next one. |
| 3 | If they are out of order, swap them. |
| 4 | Move one position right and repeat to the end (one pass). |
| 5 | Repeat passes; each pass fixes one more element at the end. |
| 6 | Stop when a full pass makes no swaps. |
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Array | Action |
|---|---|---|
| 1 | [2, 4, 1, 5] | Swap 5,2, then 5,4, then 5,1; 5 bubbles to the end. |
| 2 | [2, 1, 4, 5] | 2,4 in order; swap 4,1; 4,5 in order; 4 is now placed. |
| 3 | [1, 2, 4, 5] | Swap 2,1; the rest are already in order; 2 is placed. |
| 4 | [1, 2, 4, 5] | A full pass makes no swaps, so the array is sorted and the algorithm stops. |
When to use bubble sort
| Use it when | Avoid it when |
|---|---|
| Teaching or learning how comparison sorts work | Sorting large inputs, where O(n²) is far too slow |
The input is tiny or nearly sorted (with early exit it approaches O(n)) | You need the fastest general-purpose sort - use quicksort or merge sort |
| You need a stable, in-place sort with almost no code | The data is in random order and performance matters |
| Detecting whether a short list is already sorted in one pass | Many writes are costly (e.g. flash memory); selection sort does fewer swaps |
Bubble Sort code
A clean, runnable Bubble Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Bubble Sort code in Python
Python
1def bubble_sort(a):2 n = len(a)3 for i in range(n - 1):4 swapped = False5 for j in range(n - 1 - i):6 if a[j] > a[j + 1]:7 a[j], a[j + 1] = a[j + 1], a[j]8 swapped = True9 if not swapped:10 break # no swaps means the list is already sorted11 return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)Bubble Sort code in JavaScript
JavaScript
1function bubbleSort(a) {2 for (let end = a.length - 1; end > 0; end--) {3 let swapped = false;4 for (let j = 0; j < end; j++) {5 if (a[j] > a[j + 1]) {6 [a[j], a[j + 1]] = [a[j + 1], a[j]];7 swapped = true;8 }9 }10 if (!swapped) break; // Already sorted: stop early11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));Bubble Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void bubbleSort(int[] arr) {5 for (int i = arr.length - 1; i > 0; i--) {6 boolean swapped = false;7 for (int j = 0; j < i; j++) {8 if (arr[j] > arr[j + 1]) {9 int tmp = arr[j];10 arr[j] = arr[j + 1];11 arr[j + 1] = tmp;12 swapped = true;13 }14 }15 if (!swapped) break; // already sorted16 }17 }18
19 public static void main(String[] args) {20 int[] arr = {5, 1, 4, 2, 8, 3};21 System.out.println("Before: " + Arrays.toString(arr));22 bubbleSort(arr);23 System.out.println("After: " + Arrays.toString(arr));24 }25}Bubble Sort code in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11 for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12 bool swapped = false;13 // Each pass bubbles the largest remaining value to the end14 for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15 if (a[j] > a[j + 1]) {16 std::swap(a[j], a[j + 1]);17 swapped = true;18 }19 }20 if (!swapped) break; // already sorted21 }22}23
24int main() {25 std::vector<int> data = {5, 1, 4, 2, 8, 3};26 std::cout << "Before: ";27 printVec(data);28 bubbleSort(data);29 std::cout << "After: ";30 printVec(data);31 return 0;32}Bubble Sort code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void bubbleSort(int a[], int n) {10 for (int pass = 0; pass < n - 1; pass++) {11 bool swapped = false;12 // Each pass bubbles the largest remaining value to the end13 for (int j = 0; j < n - 1 - pass; j++) {14 if (a[j] > a[j + 1]) {15 int tmp = a[j];16 a[j] = a[j + 1];17 a[j + 1] = tmp;18 swapped = true;19 }20 }21 if (!swapped) break; // already sorted22 }23}24
25int main(void) {26 int data[] = {5, 1, 4, 2, 8, 3};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 bubbleSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}Bubble Sort FAQ
What is the time complexity of bubble sort?
Bubble sort runs in
O(n²) time in the average and worst cases because of the nested loops. With an early-exit optimization it can reach O(n) on an already-sorted array. It uses O(1) extra space.Is bubble sort stable?
Yes. Bubble sort only swaps adjacent elements when they are strictly out of order, so equal elements never pass each other and keep their original relative order.
Why is it called bubble sort?
On each pass the largest unsorted value moves step by step toward the end of the array, the way a bubble rises to the surface - hence "bubble" sort.
What is the difference between bubble sort and insertion sort?
Both run in
O(n²) and are stable and in-place, but they move data differently: bubble sort repeatedly swaps adjacent out-of-order pairs, while insertion sort takes each element and slides it back into its correct spot in the sorted prefix. Insertion sort usually does fewer writes and runs faster in practice, especially on nearly-sorted data.When should I use bubble sort instead of quicksort?
Almost never for real workloads - quicksort's
O(n log n) average time crushes bubble sort's O(n²) on anything but tiny inputs. Bubble sort is worth reaching for only when the list is very small or nearly sorted, or when you want the simplest possible stable sort for teaching.Does the early-exit optimization change bubble sort's worst case?
No. Tracking whether a pass made any swaps lets bubble sort stop early and hit
O(n) on already-sorted input, but a reverse-sorted array still needs every comparison, so the worst case stays O(n²). The optimization only helps the best and nearly-sorted cases.Related resources
More visualizations
