Bubble Sort
This page gives a brief introduction to bubble sort.
Definition
Bubble sort is a simple sorting algorithm. It takes its name from the way smaller elements slowly "float" to the top of the sequence, like bubbles, as the algorithm runs.
Procedure
Bubble sort repeatedly examines two adjacent elements and swaps them if the earlier one and the later one satisfy the given sorting condition. Once no adjacent elements need to be swapped, the sort is finished.
After \(i\) passes, the last \(i\) entries of the sequence are its \(i\) largest, so \(n-1\) passes are enough to sort the array.
Properties
Stability
Bubble sort is a stable sorting algorithm.
Time complexity
When the sequence is already fully sorted, bubble sort makes a single pass over the array and performs no swaps, so it runs in \(O(n)\).
In the worst case, it performs \(\dfrac{(n-1)n}{2}\) swaps and runs in \(O(n^2)\).
The average-case time complexity of bubble sort is \(O(n^2)\).
Implementation
Pseudocode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, NachtgeistW, Enter-tainer, iamtwz, Xeonacid, mcendu, Menci, shawlleyw, WException, TrickEye, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.