Introduction

Bubble sort and selection sort are both in-place quadratic sorting algorithms often taught early in programming courses. They look similar in Big O notation, but their operational behavior is different, especially for swap count, stability, and nearly sorted inputs. Understanding these differences helps explain when each algorithm is acceptable and why modern libraries use better alternatives.

Bubble Sort Mechanics

Bubble sort repeatedly scans adjacent pairs and swaps out-of-order neighbors. After each pass, the largest remaining element “bubbles” to the right end.

1def bubble_sort(values):
2    arr = values[:]  # keep input unchanged for demo
3    n = len(arr)
4
5    for i in range(n):
6        swapped = False
7        for j in range(0, n - i - 1):
8            if arr[j] > arr[j + 1]:
9                arr[j], arr[j + 1] = arr[j + 1], arr[j]
10                swapped = True
11        if not swapped:
12            break
13
14    return arr
15
16
17print(bubble_sort([5, 1, 4, 2, 8]))

The swapped flag provides an early exit. If no swap happens in a pass, array is already sorted.

Selection Sort Mechanics

Selection sort partitions the array into sorted prefix and unsorted suffix. Each outer pass finds minimum value in unsorted part and places it at next sorted position.

1def selection_sort(values):
2    arr = values[:]
3    n = len(arr)
4
5    for i in range(n - 1):
6        min_idx = i
7        for j in range(i + 1, n):
8            if arr[j] < arr[min_idx]:
9                min_idx = j
10
11        if min_idx != i:
12            arr[i], arr[min_idx] = arr[min_idx], arr[i]
13
14    return arr
15
16
17print(selection_sort([5, 1, 4, 2, 8]))

Selection sort does fewer swaps than bubble sort, but still scans most of the remaining array every pass.

Complexity Comparison

Both algorithms have quadratic comparison complexity in average and worst cases.

• Bubble sort worst-case comparisons: on the order of n squared.
• Selection sort worst-case comparisons: on the order of n squared.

Key differences:

• Bubble sort with early exit can be close to linear on already sorted data.
• Selection sort remains quadratic even when input is already sorted.

So Big O alone misses useful behavioral detail.

Swap Count and Write Cost

Swap behavior is often the biggest practical difference.

• Bubble sort can perform many swaps, potentially almost every inversion.
• Selection sort performs at most one swap per outer loop.

If writes are expensive, selection sort can outperform bubble sort despite similar comparison count. This matters in certain embedded or write-sensitive environments.

Stability

Stability means equal keys preserve original order after sorting.

• Bubble sort is stable in standard form when swapping only on strict greater-than.
• Selection sort is generally unstable due to long-distance swaps.

If sorting records by multiple keys across multiple passes, stability can be important.

Example record list:

records = [(2, "A"), (1, "B"), (2, "C")]

A stable algorithm keeps A before C among equal key value 2.

Practical Performance on Small Arrays

On tiny arrays, both can be acceptable for teaching or simple scripts. For production sorting, almost always use built-in language sort:

• Python uses Timsort.
• Java uses optimized hybrid strategies.
• C plus plus typically uses introspective sorting variants.

These algorithms provide near-linearithmic behavior and strong engineering optimizations.

When You Might Still Use Them

Reasonable use cases today:

• Teaching loop invariants and algorithm reasoning.
• Coding interviews focused on basics.
• Very small fixed-size lists where clarity matters more than speed.

In all other cases, built-in sort is safer and faster.

Small Benchmark Skeleton

If you want to compare empirically in Python, measure with random arrays.

1import random
2import time
3
4sample = [random.randint(0, 1000) for _ in range(200)]
5
6start = time.perf_counter()
7bubble_sort(sample)
8print("bubble", time.perf_counter() - start)
9
10start = time.perf_counter()
11selection_sort(sample)
12print("selection", time.perf_counter() - start)

Keep dataset and environment constant for fair comparison.

Common Pitfalls

A common pitfall is assuming equal Big O means equal runtime under real data conditions. Another issue is using plain bubble sort without early-exit optimization, which overstates work on nearly sorted input. Teams also overlook stability requirements and pick selection sort where stable order is needed. Benchmarking with tiny arrays only can produce misleading conclusions. Finally, implementing custom sort in production where built-in sort exists usually increases risk without clear benefit.

Summary

• Bubble and selection sort are both in-place quadratic algorithms.
• Bubble sort can be adaptive with early exit and is usually stable.
• Selection sort uses fewer swaps but is typically unstable.
• Both are mainly educational for modern software engineering.
• For real workloads, prefer standard library sorting implementations.
• Use algorithm comparisons to learn tradeoffs, not to justify replacing proven built-in sorts.