# Bubble, Selection, Insertion Sort — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/bubble-selection-insertion

> The three O(n^2) sorts — simple, in place, good for tiny or nearly-sorted inputs.

## How each one moves data

**Bubble**: repeatedly swap adjacent out-of-order pairs; large values "bubble" to the end. **Selection**: each pass finds the minimum of the rest and puts it next. **Insertion**: take the next element and slide it left into its sorted place.

## Insertion sort

The best of the three in practice: `O(n)` on nearly-sorted data and stable.

```python
def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift right
            j -= 1
        a[j + 1] = key        # drop key in place
    return a
```

## Complexity & stability

All three: `O(n^2)` average/worst, `O(1)` space. Insertion is `O(n)` best case. Bubble and insertion are **stable** (keep equal elements' order); selection is not. Selection does the fewest swaps (`O(n)`).

## Reality check

In production you call the library sort. These matter for interviews and as the base case inside faster sorts (e.g. Timsort uses insertion sort on small runs).