Elementary Sorting: Bubble, Selection and Insertion

Sorting rearranges a collection so that its keys follow a specified order. Records often contain more than the key used for comparison: employees may be ordered by department, dates or salary while retaining all other fields. A correct sorting algorithm must produce a permutation of the original records and place every adjacent output pair in the order defined by the comparator.

Sorting improves later operations. Binary search requires ordered input, duplicate values become adjacent, merging becomes efficient and reports become easier to group. No single sorting method is best for every input. Size, existing order, memory, stability, write cost and worst-case guarantees all affect the choice.

Properties Used to Compare Sorts

An algorithm is stable if records with equal keys retain their original relative order. Suppose two records have equal score and originally appear as A before B. A stable score sort keeps A before B. Stability lets multiple sorts compose: a stable sort by department after a sort by name preserves name order within each department.

An in-place sort uses only a constant amount of auxiliary storage apart from its input, though definitions sometimes permit logarithmic recursion space. This describes extra memory, not speed or stability.

An adaptive sort benefits from existing order. A nearly sorted input requires less work than a badly disordered input. An online algorithm can incorporate items as they arrive rather than requiring the full input first. Insertion sort has both useful properties.

A comparison sort obtains order information by comparing keys. Its cost can be separated into comparisons, swaps, assignments and auxiliary memory. This matters because writing a large record or flash-storage location may cost much more than comparing two small keys.

An inversion is a pair of positions i < j for which a[i] > a[j] in ascending order. A sorted array has zero inversions; a reverse-sorted array with distinct elements has n(n - 1)/2. Inversions measure disorder and help explain bubble and insertion sort.

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them when they are inverted. In a left-to-right pass through active positions 0 to end, a larger value moves right whenever it meets a smaller neighbor. At the end of the pass, the largest value in that active range has reached position end.

The outer loop then shortens the active range because the placed suffix is already final. A useful invariant is: before each pass ending at end, all positions after end contain the correct largest elements in sorted order. During the pass, the largest value seen so far occupies the current comparison’s right position.

For example, a first pass over 5, 1, 4, 2 performs:

5, 1, 4, 2
1, 5, 4, 2
1, 4, 5, 2
1, 4, 2, 5

The value 5 is now final. Later passes sort the prefix.

A common optimization records whether a pass made any swap. If an entire pass makes none, every adjacent pair is already ordered, which implies the whole active range is sorted, so the algorithm can stop. With this flag, sorted input takes Theta(n) comparisons. Without early stopping, the loops still perform Theta(n²) comparisons on sorted input.

Worst-case and average time are Theta(n²). Reverse order causes approximately n(n - 1)/2 comparisons and swaps. Each adjacent swap removes exactly one inversion, so bubble sort performs as many swaps as the initial inversion count. This makes it adaptive in movement count, while its optimized comparison count becomes especially good only when passes quickly find no swaps.

Ordinary bubble sort is stable when it swaps only if the left key is strictly greater. Equal keys are never exchanged directly, so they cannot cross. It uses O(1) auxiliary space. Its many swaps usually make it unattractive for large arrays despite its simplicity.

Selection Sort

Selection sort divides the array into a sorted prefix and an unsorted suffix. For each position i, it scans positions i through n - 1 to find the smallest remaining key, then swaps that record into position i.

The loop invariant is: before iteration i, positions 0 through i - 1 contain the i smallest input elements in their final sorted positions. The scan identifies the minimum of the remaining suffix, so placing it at i extends the invariant by one.

Selection sort performs the same triangular number of comparisons regardless of input order:

(n - 1) + (n - 2) + ... + 1 = n(n - 1)/2

Its best, average and worst comparison time is therefore Theta(n²). It makes at most n - 1 swaps and an implementation can avoid a self-swap when the minimum is already at i. This low movement count can be useful when writes are unusually expensive.

The ordinary distant-swap form is not stable. Consider tagged equal keys 2A, 2B, 1. Selecting 1 and swapping it with 2A produces 1, 2B, 2A, reversing the equal records. A stable selection variant can remove the minimum and shift intervening values instead of swapping, but that increases movement.

Selection sort is in-place and simple, but it does not adapt to existing order because it must search the entire remaining suffix to prove which item is minimum. It can be reasonable for small collections when minimizing swaps matters more than minimizing comparisons.

Insertion Sort

Insertion sort maintains a sorted prefix and inserts the next item into its correct position within that prefix. It resembles arranging playing cards in a hand: take one new card, shift larger cards aside and place the card in the resulting gap.

At outer-loop index i, save a[i] as the current value. Starting at i - 1, move each larger prefix element one position to the right. When a value no greater than the current value is found or the beginning is passed, place the saved value in the open position. The invariant is that a[0..i-1] is sorted before the iteration and a[0..i] is sorted afterward.

For 5, 2, 4, the first insertion saves 2, shifts 5 and produces 2, 5, 4. The next insertion saves 4, shifts 5 and produces 2, 4, 5.

On already sorted input, the inner condition fails after one comparison for each new item. Best-case time is Theta(n). On reverse-sorted input, every new item crosses the entire prefix, producing Theta(n²) comparisons and movements. Average time is also Theta(n²) under common input assumptions.

Insertion sort’s work is closely related to inversion count. Each one-position shift removes one inversion, giving time O(n + I) where I is the number of inversions. This explains why it performs well on nearly sorted data even when n is moderately large.

The usual implementation is stable when it shifts keys strictly greater than the saved key. It inserts after existing equal keys. Using a greater-than-or-equal comparison would move the new equal item before older equals and destroy stability. Insertion sort is in-place and online and its tight inner loop has low overhead.

Binary search can find the insertion position in O(log n) comparisons, but inserting into an array still shifts up to O(n) elements. Binary insertion sort can reduce expensive comparisons while retaining quadratic movement. With a linked list and a known insertion location, relinking is constant-time, but discovering that location still requires traversal unless another structure supplies it.

Why Quadratic Sorts Still Matter

For large arbitrary inputs, O(n log n) algorithms normally outperform quadratic methods. For small arrays, the simpler loops and locality of insertion sort can be faster than a more elaborate algorithm. Practical merge sort and quicksort implementations often switch to insertion sort on small subarrays.

Selection sort offers predictable comparisons and few swaps. Bubble sort exposes adjacent-exchange behavior and can detect an already sorted sequence. Insertion sort is usually the strongest practical choice among the three because it is adaptive, stable, compact and efficient for small or nearly ordered data.

Input representation also matters. Array-based insertion shifts records efficiently through contiguous memory. Bubble sort on a linked list avoids moving entire records but still performs quadratic comparisons. Selection of an algorithm should consider actual operations and hardware, rather than asymptotic time alone.

Comparators and Correct Ordering

A comparator must behave consistently. It should report negative, zero or positive according to whether its first argument belongs before, is equivalent to or belongs after the second. A well-formed comparison order is transitive: if a < b and b < c, then a < c. Contradictory comparison results can make any sorting algorithm produce unpredictable output.

Avoid computing an integer comparison as a - b, because subtraction can overflow and reverse the apparent sign. Use explicit relational comparison or a library comparison method. For records, compare the primary key and then any required tie-breakers. Adding a unique tie-breaker eliminates comparator equality; retaining equality allows a stable algorithm to preserve original order.

Tracing and Verifying a Sort

A trace should show the invariant boundary, comparisons and movements after each outer iteration. Looking only at the final array can hide an incorrect algorithm that happens to work on one input. Boundary inputs include an empty array, one item, sorted and reverse-sorted sequences, duplicate keys, all-equal keys and extreme numeric values.

Verification has two parts. Order checks that no adjacent output pair is inverted. Permutation preservation checks that every input record appears exactly as many times in the output. Stability tests require tagged records with equal keys; plain equal integers cannot reveal whether their identities were reversed.

The elementary sorts demonstrate three different ways to grow a sorted region. Bubble sort fixes a largest suffix through adjacent exchanges, selection sort places a chosen minimum into a final prefix and insertion sort integrates each new item into a sorted prefix. Understanding those invariants makes their correctness and performance predictable.