# Bubble Sort

URL: https://softwaredictionary.org/terms/bubble-sort
Category: Data Structures
Last updated: 2026-10-03
In Turkish: kabarcık sıralaması
Pronunciation: BUB-ul SORT

In short: Bubble sort is a simple sorting algorithm that keeps swapping out-of-order neighbors, so each pass carries the largest remaining value to the end.

## What is bubble sort?

Each pass compares every pair of neighbors and swaps them if the left one is bigger. After the first pass, the largest element has moved all the way to the end; after the second, the second largest sits just before it, and so on. The sorted part grows from the right until a pass makes no swaps, which means the list is in order.

Bubble sort takes O(n²) time in the average and worst cases, because each of up to n passes may compare up to n pairs. With the common optimization of stopping when a pass makes no swaps, an already sorted list takes just one pass, O(n). It sorts in place with O(1) extra memory and is stable, keeping equal elements in their original order.

Its value is educational. It is easy to understand, visualize and implement, which makes it a common first sorting algorithm and a good way to learn about loops, swaps, complexity and stability. Watching it run shows clearly why some algorithms scale far better than others.

A common misconception is that bubble sort is acceptable for real data. It is far slower than the alternatives on anything but tiny or nearly sorted inputs; even insertion sort, which is also O(n²), usually beats it. Production code should use the language's built-in sort, which uses efficient algorithms such as Timsort or introsort.

## Key takeaways

- Bubble sort repeatedly swaps neighboring elements that are out of order.
- Each pass moves the largest remaining element to the end.
- It is O(n²) on average, O(n) on sorted input with early exit.
- It is in-place and stable, and mainly used for teaching.
- Real code should use the built-in sort instead.

## Example: Bubble sort with an early exit (Python)

```python
def bubble_sort(items):
    items = list(items)
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]   # swap neighbors
                swapped = True
        if not swapped:      # no swaps: already sorted, stop early
            break
    return items

print(bubble_sort([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]
```

## Frequently asked questions

**Why is bubble sort slow?**

Because it moves elements only one position at a time and may need about n passes over n elements, giving O(n²) comparisons. Doubling the input roughly quadruples the work.

**Is bubble sort stable?**

Yes. It only swaps neighbors when the left one is strictly greater, so equal elements never pass each other and keep their original order.

**What is the difference between bubble sort and insertion sort?**

Both are O(n²) in the worst case. Bubble sort swaps neighbors across the whole list on each pass, while insertion sort builds a sorted prefix and inserts each new element into place, which usually does far fewer operations.

---

Software Dictionary: https://softwaredictionary.org/ · https://softwaredictionary.org/llms.txt