Bubble sort is one of the simplest comparison-based sorting algorithms. It repeatedly scans a list, compares adjacent elements and swaps them when they are in the wrong order. The algorithm gets its informal name from the way small or large values move ("bubble") toward their final positions as the passes proceed. Because of its simplicity it is commonly used in introductory teaching and simple scripts, though other algorithms are usually chosen for performance-sensitive tasks. For further background see additional notes on bubble sort.
How it works
At a high level the algorithm makes multiple passes over the array. On each pass it compares each pair of neighboring items and swaps them if they are out of order. After the first pass the largest element will have moved to the end of the array; after the second pass the next largest has settled into place, and so on. The process stops when a complete pass makes no swaps, indicating the list is sorted.
- Start at the beginning of the list.
- Compare the current element and the next element.
- If they are out of order, swap them.
- Move one position forward and repeat until the end of the pass.
- Repeat passes until no swaps occur on a pass.
Complexity and characteristics
Bubble sort operates in-place using only a constant amount of extra memory. It is a stable sorting method (equal elements keep their relative order). Typical time complexity is O(n^2) comparisons and swaps in the average and worst cases, which makes it impractical for large datasets. With a simple optimization that stops early when no swaps are made, the best-case complexity becomes O(n) for an already-sorted list.
Variants and comparisons
Several small variants exist. A common improvement is adding a swapped-flag to exit early. The cocktail shaker sort (bi-directional bubble) alternates passes left-to-right and right-to-left to move both large and small elements faster. Compared with selection or insertion sort, bubble sort is often slower, though its conceptual simplicity is why it remains popular for teaching. For an interactive demonstration try a visualization.
Example: given [5, 1, 4, 2, 8], a first pass will compare 5 and 1 (swap), then 5 and 4 (swap), then 5 and 2 (swap), then 5 and 8 (no swap), leaving 5 at the end. Repeating passes eventually produces the sorted sequence [1, 2, 4, 5, 8]. Bubble sort's clear mechanics and low implementation cost make it useful for small or nearly-sorted inputs, diagnostic code, and classroom demonstrations rather than production-scale sorting.