Insertion and selection sort: passes, invariants and stability
Goal and prerequisites
An array is sorted by key in nondecreasing order when each key is at most the next key. Sorting must preserve every input record exactly once; merely writing a sorted sequence of unrelated keys is not a sort. We study two comparison sorts and the particular implementations below, not every possible variant.
Prerequisites: array elements and valid indices; array parameters and caller-visible changes; algorithm growth and asymptotic bounds. You should distinguish a tight Θ bound from an O upper bound and distinguish best-case inputs from worst-case inputs. Here n is the active prefix length. Empty and singleton prefixes are already sorted and need zero passes.
A pass means one execution of the outer loop body. For n >= 1, both versions execute exactly n - 1 passes, even if a pass moves nothing. For n = 0 they execute zero passes. Never substitute the number of swaps or the number of comparisons for the number of passes.
Records and stability: syntax before algorithms
A key says where a record belongs; an identity says which original record it is. In notation [2a, 2b, 1c], a and b label distinct records with the same key 2. Only the numeric key participates in comparisons. A stable sort preserves the original relative order of equal-key records, so a must remain before b. Stability does not mean that records stay at their original indices.
Our C declaration is struct Record { int key; int id; };. A struct groups two int fields. struct Record item declares one such record; a[i].key accesses the key field of array element i. Assignment a[j] = a[j-1] copies both fields, keeping key and identity together. {{2,0},{2,1},{1,2}} initializes three records in field order; unused array elements are zero-initialized. IDs 0,1,2 correspond to labels a,b,c in the example. The algorithm does not compare IDs.
struct Record a[CAP] in a function parameter adjusts to a pointer; it does not copy the input array or prove its capacity. Our caller promises a live, writable array of CAP records, with initialized active elements and 0 <= n <= CAP. Calls sort the prefix a[0..n-1] in place and preserve unused elements. The NULL and n checks reject obvious invalid arguments, but cannot detect a dangling pointer or an undersized array. Even n = 0 requires a non-NULL live array under this contract. No dynamic allocation is needed.
enum { CAP = 8 }; defines the demonstration capacity. ++i increments, --j decrements, and && evaluates its right side only when its left side is true. Thus j > 0 && a[j-1].key > item.key never reads a negative index. Direct key comparisons are safe for INT_MIN and INT_MAX; subtracting two keys to compare them could overflow.
Insertion sort: grow a sorted prefix
At outer index i, save record a[i] as item. The prefix before i is already sorted. Move every strictly larger preceding record one position right, stopping at the beginning or at a key <= item's key. Put item into the resulting hole.
Outer-loop invariant, just before pass i (1 <= i < n): a[0..i-1] is a sorted, stable permutation of the original first i records; a[i..n-1] has not yet been touched. Initially i = 1, so the one-record prefix satisfies this. The pass inserts the next original record after all earlier equal records, maintaining both order and stability. At termination the whole active prefix is sorted and all original records are preserved.
During shifting, the saved item is outside the array and j denotes a hole: the displaced records that were at positions j through i-1 at the start of this pass now occupy j+1 through i, all with keys greater than item.key. The physical contents of the hole may temporarily duplicate another record, so do not claim the array by itself remains a permutation after every individual assignment. The saved item plus the non-hole records preserve the data. Writing item at j restores the full permutation.
The strict > matters: an earlier equal key is not shifted past the new item. Replacing it with >= could reverse equal records and would invalidate the stability claim.
Worked trace 1: insertion passes
Input [4a, 2b, 3c, 2d]. The vertical bar marks the sorted prefix after each pass.
- Start: [4a | 2b, 3c, 2d].
- Pass i=1: save 2b; shift 4a right; insert at 0. [2b, 4a | 3c, 2d].
- Pass i=2: save 3c; shift 4a; compare 2b with 3c and stop. [2b, 3c, 4a | 2d].
- Pass i=3: save 2d; shift 4a then 3c; comparison 2b.key > 2d.key is false. [2b, 2d, 3c, 4a |].
There are three passes, four right shifts, and six key comparisons (1+2+3). A key comparison means an executed a[j-1].key > item.key, including its false result; the boundary test j > 0 is not counted. Pass 1 ends at j=0, so it has no final false key comparison. Equal-key order b before d is preserved.
Selection sort: finalize one position per pass
At index i, start min_index=i. Scan j=i+1 through n-1, replacing min_index only when a[j].key is strictly smaller. Therefore it selects the first occurrence of the minimum key in the current suffix. After the complete scan, swap that record with a[i], unless min_index already equals i. This is ordinary swap-based selection sort, not the different stable variant that removes a minimum and shifts intervening records.
Outer-loop invariant before pass i: prefix a[0..i-1] is sorted, every key there is <= every key in the remaining suffix, and the entire array is a permutation of the input records. Initially the prefix is empty. During the inner scan, min_index points to the first minimum in a[i..j-1], the portion already considered. Comparing the next record extends this fact by one position. Once the suffix is scanned, moving its minimum to i extends the finalized prefix. Swapping preserves records. After n-1 passes, only the last record remains, and it is no smaller than the prefix: the entire array is sorted.
These invariants say nothing about equal-record order. Selecting a first minimum does not make a long-distance swap stable.
Worked trace 2: selection passes
Use the same input [4a, 2b, 3c, 2d].
- Pass i=0: scan 2b,3c,2d; strict < keeps the first minimum 2b. Swap positions 0 and 1: [2b | 4a, 3c, 2d].
- Pass i=1: suffix minimum is 2d at 3. Swap positions 1 and 3: [2b, 2d | 3c, 4a].
- Pass i=2: compare 4a with 3c; minimum is already at 2. No swap: [2b, 2d, 3c | 4a]. This still counts as a pass.
There are three passes, six key comparisons (3+2+1) and two actual swaps. Equal order happens to survive this input. That observation does not prove stability on all inputs.
Worked trace 3: a stability counterexample
Input [2a, 2b, 1c]. Selection's first pass swaps 2a with 1c, giving [1c, 2b, 2a]. The next pass compares equal 2 keys, keeps the first minimum, and does not swap. Final b before a reverses the original equal-key order. Thus this selection variant is unstable even with strict < and first-minimum selection.
Insertion's first pass leaves [2a,2b] alone. Its next pass saves 1c, shifts 2b and then 2a, and yields [1c,2a,2b]. The pair's relative order survives. Stability is a guarantee over all permitted inputs, while instability needs only one counterexample.
Complete bounded C11 program
The following is the complete source in sorting.c. main calls both sorting functions inside an explicit success check and returns 1 if either fails. Sorting still executes if NDEBUG is defined. The separate test program uses assert and must be built without NDEBUG.
#include <limits.h>
#include <stdio.h>
enum { CAP = 8 };
struct Record { int key; int id; };
/* The caller supplies a live CAP-element array, even when n is zero. */
int insertion_sort(struct Record a[CAP], int n) {
if (a == NULL || n < 0 || n > CAP) { return 0; }
for (int i = 1; i < n; ++i) {
struct Record item = a[i];
int j = i;
while (j > 0 && a[j - 1].key > item.key) {
a[j] = a[j - 1];
--j;
}
a[j] = item;
}
return 1;
}
int selection_sort(struct Record a[CAP], int n) {
if (a == NULL || n < 0 || n > CAP) { return 0; }
for (int i = 0; i < n - 1; ++i) {
int min_index = i;
for (int j = i + 1; j < n; ++j) {
if (a[j].key < a[min_index].key) { min_index = j; }
}
if (min_index != i) {
struct Record temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
return 1;
}
static void print_records(const struct Record a[CAP], int n) {
for (int i = 0; i < n; ++i) {
printf("%s%d(%d)", i == 0 ? "" : " ", a[i].key, a[i].id);
}
putchar('\n');
}
int main(void) {
struct Record insertion[CAP] = {{2, 0}, {2, 1}, {1, 2}};
struct Record selection[CAP] = {{2, 0}, {2, 1}, {1, 2}};
if (!insertion_sort(insertion, 3) || !selection_sort(selection, 3)) {
return 1;
}
printf("insertion: "); print_records(insertion, 3);
printf("selection: "); print_records(selection, 3);
return 0;
}Exact output (key followed by original ID in parentheses):
insertion: 1(2) 2(0) 2(1) selection: 1(2) 2(1) 2(0)
Both functions return 1 on success, including valid empty/singleton prefixes, or 0 for a NULL pointer or n outside 0..CAP. Invalid calls return before any writes. The caller's capacity/lifetime promise remains necessary. print_records reads only active elements. Its static declaration limits this helper's name to this source file. The conditional expression i == 0 ? "" : " " chooses an empty string for the first record and a one-space string for later records, avoiding a leading space. printf's %s prints that string, while each %d prints an int; putchar writes a newline.
Counts, input cases and space
Count only executed comparisons of two record keys, not loop bounds, index tests or assignments. For selection, each pass compares every remaining candidate against the running minimum: (n-1)+(n-2)+...+1 = n(n-1)/2 key comparisons for n >= 1, and zero when n=0. This is independent of input order, including already-sorted input. It performs at most n-1 actual swaps; this program skips self-swaps. Zero swaps does not mean zero work.
For insertion, sorted nondecreasing input, including an all-equal array, uses exactly n-1 key comparisons and zero right shifts for n >= 1. Each pass still saves and writes item. Strictly decreasing input with distinct keys uses 1+2+...+(n-1) = n(n-1)/2 key comparisons and that many shifts. A shift is a rightward record assignment inside the while loop, not the final insertion assignment. Other inputs can have a failed stopping comparison as well as successful shift comparisons.
For the conventional scalable algorithms under a constant-cost record/key model, insertion's best-case time is Θ(n), its worst-case time is Θ(n²); selection's best- and worst-case time are Θ(n²). These are asymptotic statements as n grows (n >= 2), not different interpretations of O versus Θ. Both use Θ(1) auxiliary space: a constant number of indices plus one saved record. Their input array occupies Θ(n) space and is not auxiliary. The two separate arrays in main compare the two algorithms on identical inputs; an individual sorting call does not create a hidden array copy. The test harness makes copies to verify results, outside either sorting algorithm.
CAP=8 deliberately bounds the executable and its index arithmetic. Literally, all runs of this fixed program have a finite constant bound. The asymptotic claims concern the same algorithms applied to larger permitted arrays, not growth beyond this program's declared capacity. The n(n-1)/2 expression is a mathematical count, not evaluated by the sorting code. At n=0 or 1, both routines take constant setup time with zero passes and key comparisons.
Key box: exam traps
- Sort whole records, compare only keys; stability concerns equal keys' original order.
- Strict > shifting gives this insertion sort stability. Strict < first-minimum selection does not save swap-based selection from instability.
- An invariant must state what is true before each pass and why one pass preserves it.
- An already-sorted array still receives n-1 passes when n>=1. Selection still scans every suffix; insertion stops each shift loop immediately.
- A no-op selection pass is not a swap. A final insertion write is not a right shift. State exactly which operation is counted.
- Θ(1) auxiliary space does not mean the input array has constant size in the scalable model.
Two extra exercises with solutions
- Trace both methods on [3a,1b,2c]. Give every end-of-pass state and the key-comparison count.
Solution: insertion gives [1b,3a,2c], then [1b,2c,3a], with 1+2=3 key comparisons and two shifts. Selection gives [1b,3a,2c], then [1b,2c,3a], with 2+1=3 comparisons and two swaps. Matching states here do not make the algorithms identical.
- Change insertion's while comparison to >= and sort [2a,2b,1c]. What changes?
Solution: first pass shifts 2a and inserts 2b before it: [2b,2a,1c]. Second pass shifts both 2 records and inserts 1c: [1c,2b,2a]. Keys are sorted but equal identities reverse, so stability is lost. On all-equal length n>=1 input, this changed variant performs n(n-1)/2 shifts and key comparisons instead of the original variant's zero shifts and n-1 comparisons.
The six following questions are original practice, each with exactly one correct option.
S01
After two complete insertion-sort passes on [4a,2b,3c,2d], what is the array?
A. [2b,3c,4a,2d] B. [2b,2d,3c,4a] C. [2b,4a,3c,2d] D. [4a,2b,2d,3c]
Answer: A
A is correct: passes i=1 and i=2 insert 2b and then 3c into the prefix; 2d remains untouched.
B is incorrect: that is the fully sorted result after the third pass.
C is incorrect: that is the result after only the first pass.
D is incorrect: insertion sorts the growing left prefix, not the rightmost pair first.
S02
For the stated selection sort, a sorted array of five distinct keys receives how many passes, key comparisons and actual swaps?
A. 0 passes, 0 comparisons, 0 swaps B. 4 passes, 4 comparisons, 0 swaps C. 4 passes, 10 comparisons, 0 swaps D. 5 passes, 10 comparisons, 5 swaps
Answer: C
A is incorrect: this implementation does not skip its scans after recognizing sorted order.
B is incorrect: four comparisons describes insertion on this input, not selection; selection scans all suffix candidates.
C is correct: n-1=4 passes and 4+3+2+1=10 key comparisons occur; min_index=i each time so no swap occurs.
D is incorrect: the final singleton suffix needs no pass, and self-swaps are explicitly skipped.
S03
Sorting [2a,2b,1c] by key only, which pair of final arrays matches the stated insertion and selection versions, respectively?
A. [1c,2b,2a]; [1c,2a,2b] B. [1c,2a,2b]; [1c,2b,2a] C. [1c,2a,2b]; [1c,2a,2b] D. [2a,2b,1c]; [1c,2b,2a]
Answer: B
A is incorrect: it reverses the outcomes; strict-greater insertion preserves a before b.
B is correct: insertion preserves the equal pair, while selection first swaps 2a and 1c, placing b before a.
C is incorrect: first-minimum selection still moves 2a across 2b in its first long-distance swap.
D is incorrect: insertion does insert 1c at the front; stability does not prohibit movement.
S04
Before selection pass i, which statement is the correct outer-loop invariant for this implementation?
A. The suffix is sorted, while the prefix may be arbitrary. B. The prefix contains exactly the first i original records in stable order. C. Equal-key records everywhere retain their original relative order. D. The prefix is sorted, each prefix key is <= every suffix key, and all original records remain.
Answer: D
A is incorrect: selection finalizes the left prefix; it need not sort the remaining suffix.
B is incorrect: that describes insertion's processed-original-prefix property; selection can bring a record from anywhere in the suffix.
C is incorrect: swap-based selection is unstable, as [2a,2b,1c] demonstrates.
D is correct: placing the suffix minimum next extends this prefix property, and swaps preserve the full collection of records.
S05
For n>=2 under the scalable constant-cost model, which time-bound statement is tight for these implementations?
A. Insertion best Θ(n), worst Θ(n²); selection best and worst Θ(n²). B. Both algorithms have best and worst Θ(n). C. Insertion best Θ(1); selection best Θ(1) when sorted. D. Insertion is always Θ(n²); selection is always Θ(n log n).
Answer: A
A is correct: insertion quickly stops each pass on sorted input, whereas selection always scans every remaining suffix candidate.
B is incorrect: reverse distinct keys force quadratically many insertion shifts, and selection comparisons are quadratic regardless of order.
C is incorrect: both still execute n-1 passes; selection additionally performs n(n-1)/2 comparisons.
D is incorrect: insertion has a linear best case, and this selection algorithm has a quadratic, not n log n, scan count.
S06
In insertion sort, why is j > 0 evaluated before a[j-1].key > item.key?
A. It makes selection sort stable. B. It prevents integer overflow by subtracting keys. C. With && short-circuiting, it prevents reading a[-1] when the hole reaches index 0. D. It proves that any non-NULL pointer has CAP live elements.
Answer: C
A is incorrect: this guard is in insertion, and stability comes from the strict key comparison rather than the boundary test alone.
B is incorrect: the code directly compares keys without subtraction; j>0 protects an array index.
C is correct: when j=0, && skips its right operand, so j-1 is not used as an array index.
D is incorrect: capacity and lifetime remain caller promises; a boundary check cannot establish pointer validity.
Sign in to keep your progress. Sign in