Elementary sorting
The three algorithms in this lesson sort in place with two nested loops, which makes them quadratic and easy to check. They are the reference every faster sort is measured against, and the one to use for a handful of elements. All three receive a pointer and a count, the interface from lesson 28.
Insertion sort
Insertion sort keeps the left part of the array sorted and inserts each new element into its place by shifting larger values right. It is stable, it works well on data that is nearly sorted, and its inner loop stops as soon as the right slot is found.
#include <stdio.h>
static void insertion_sort(int *values, int count)
{
for (int i = 1; i < count; i++) {
int value = values[i];
int j = i - 1;
while (j >= 0 && values[j] > value) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = value;
}
}
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
insertion_sort(values, 5);
for (int i = 0; i < 5; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra insertion.c -o insertion
./insertion
1 2 5 6 9
The saved value is what makes the shifting safe: the slot at i is overwritten early, but the value lives in a local until the loop finds its place. The comparison values[j] > value must come after the j >= 0 test, or the loop reads before the array.
Selection sort
Selection sort finds the smallest remaining element and swaps it into the next position. It always makes the same number of comparisons, whatever the input order, and at most one swap per position. That predictability is useful when writing to the array is expensive.
#include <stdio.h>
static void selection_sort(int *values, int count)
{
for (int i = 0; i < count - 1; i++) {
int smallest = i;
for (int j = i + 1; j < count; j++) {
if (values[j] < values[smallest]) {
smallest = j;
}
}
int temporary = values[i];
values[i] = values[smallest];
values[smallest] = temporary;
}
}
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
selection_sort(values, 5);
for (int i = 0; i < 5; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra selection.c -o selection
./selection
1 2 5 6 9
The inner loop starts at i + 1, because the element at i is the current candidate. Selection sort is not stable: the swap moves an element past equal ones, which matters when the array holds records with a separate key.
Bubble sort
Bubble sort compares neighbouring pairs and lets the largest element travel to the end of each pass. The early exit makes it linear on an array that is already sorted, which is its one advantage. Without the flag it always does the full quadratic number of passes.
#include <stdio.h>
static void bubble_sort(int *values, int count)
{
for (int pass = 0; pass < count - 1; pass++) {
int swapped = 0;
for (int j = 0; j < count - 1 - pass; j++) {
if (values[j] > values[j + 1]) {
int temporary = values[j];
values[j] = values[j + 1];
values[j + 1] = temporary;
swapped = 1;
}
}
if (!swapped) {
break;
}
}
}
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
bubble_sort(values, 5);
for (int i = 0; i < 5; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra bubble.c -o bubble
./bubble
1 2 5 6 9
After each pass the last pass elements are already in place, which is why the inner bound shrinks. The - 1 is there for the pair j + 1; without it the last comparison reads past the array, the mistake at the end of this lesson.
Comparing the three
Counting comparisons and moves shows why the choice matters. The same array goes through insertion sort and selection sort, with counters incremented in the loops. Insertion sort stops its inner loop early on this input, so it compares less; selection sort always scans the whole remaining array.
#include <stdio.h>
static int comparisons = 0;
static int moves = 0;
static void insertion_sort(int *values, int count)
{
for (int i = 1; i < count; i++) {
int value = values[i];
int j = i - 1;
while (j >= 0 && (comparisons++, values[j] > value)) {
values[j + 1] = values[j];
moves++;
j--;
}
values[j + 1] = value;
moves++;
}
}
static void selection_sort(int *values, int count)
{
for (int i = 0; i < count - 1; i++) {
int smallest = i;
for (int j = i + 1; j < count; j++) {
comparisons++;
if (values[j] < values[smallest]) {
smallest = j;
}
}
int temporary = values[i];
values[i] = values[smallest];
values[smallest] = temporary;
moves += 3;
}
}
int main(void)
{
int a[5] = {5, 2, 9, 1, 6};
int b[5] = {5, 2, 9, 1, 6};
insertion_sort(a, 5);
printf("insertion: %d comparisons, %d moves\n", comparisons, moves);
comparisons = 0;
moves = 0;
selection_sort(b, 5);
printf("selection: %d comparisons, %d moves\n", comparisons, moves);
return 0;
}
gcc -Wall -Wextra compare.c -o compare
./compare
insertion: 7 comparisons, 9 moves
selection: 10 comparisons, 12 moves
Selection sort made 4 + 3 + 2 + 1 = 10 comparisons, the fixed cost for five elements. Insertion sort made 7 because two inner loops stopped before the start of the array. Both are quadratic in the worst case, which is why lesson 48 moves to divide and conquer.
A short loop and a bad swap
A bubble sort whose inner bound subtracts one too many skips the last pair of every pass. The program compiles and prints an array that is almost sorted, which is worse than a crash because it looks plausible:
#include <stdio.h>
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
int count = 5;
for (int pass = 0; pass < count - 1; pass++) {
for (int j = 0; j < count - 2 - pass; j++) {
if (values[j] > values[j + 1]) {
int temporary = values[j];
values[j] = values[j + 1];
values[j + 1] = temporary;
}
}
}
for (int i = 0; i < count; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra nowrong.c -o nowrong
./nowrong
1 2 5 9 6
6 never reached its place because the pair (9, 6) was never compared. The correct bound is count - 1 - pass, which subtracts only the elements already placed at the end.
The second mistake is a loop that runs one element past the array. When the array and the bound are both constants, the optimiser proves the overrun and reports it even though the sort still produces the right output:
#include <stdio.h>
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
for (int i = 1; i <= 5; i++) {
int value = values[i];
int j = i - 1;
while (j >= 0 && values[j] > value) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = value;
}
for (int i = 0; i < 5; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -O2 -Wall -Wextra bounds2.c -o bounds2
bounds2.c: In function 'main':
bounds2.c:8:13: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
8 | int value = values[i];
| ^~~~~
bounds2.c:7:23: note: within this loop
7 | for (int i = 1; i <= 5; i++) {
| ~~^~~~
The last pass reads values[5] and writes the saved value back into the array at an index one past the end. It is not run here, because the read may return anything and the write corrupts the stack.
Exercises
- Add a counter to bubble sort and compare its comparisons on a sorted array, a reversed array and a random one.
- Sort an array of structs by one field with insertion sort, keeping the sort stable.
- Binary search the sorted array from the last section and print the index of every value the program reads.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does insertion sort place each new element?
Answer
It shifts larger values right and inserts the saved value
The value at
iis saved, larger elements move one place right, and the value goes into the gap. -
What is fixed about selection sort's comparison count?
Answer
It always scans the whole remaining range
Every pass scans all remaining elements, so the count depends only on the array length and not on the input order.
-
What is the advantage of bubble sort with a swapped flag?
Answer
It stops early on an already sorted array
A pass with no swaps proves the array is ordered, so the loop can stop instead of running every pass.
-
Which of the three elementary sorts is stable?
Answer
Insertion sort, because it shifts instead of swapping
Insertion sort moves an element past only larger values, so equal elements keep their relative order.
-
What does this program print?
#include <stdio.h> static void insertion_sort(int *v,int n){ for(int i=1;i<n;i++){ int x=v[i],j=i-1; while(j>=0&&v[j]>x){v[j+1]=v[j];j--;} v[j+1]=x; } } int main(void){ int v[5]={5,2,9,1,6}; insertion_sort(v,5); for(int i=0;i<5;i++) printf("%d ",v[i]); printf("\n"); return 0; }Answer
1 2 5 6 9
Insertion sort shifts larger values right and places each saved value in its sorted position.
-
What does this program print?
#include <stdio.h> static int comps=0,moves=0; static void insertion_sort(int *v,int n){ for(int i=1;i<n;i++){ int x=v[i],j=i-1; while(j>=0&&(comps++,v[j]>x)){v[j+1]=v[j];moves++;j--;} v[j+1]=x;moves++; } } int main(void){ int v[5]={5,2,9,1,6}; insertion_sort(v,5); printf("insertion: %d comparisons, %d moves\n",comps,moves); return 0; }Answer
insertion: 7 comparisons, 9 moves
Two inner loops stop before the start of the array, so insertion compares seven times on this input.
-
What does the bubble sort with the short inner bound print?
Answer
1 2 5 9 6, with 6 left near the end
The pair
9 6is never compared because the bound stops one pair early, so 6 never moves into place. -
What does GCC report for the insertion loop with
i <= 5on a five-element array?Answer
Iteration 4 invokes undefined behaviour
The last pass reads
values[5]and writes past the array, and the optimiser reports the bad iteration. -
Why is the saved
valueneeded in insertion sort?Answer
The slot is overwritten before its old value is placed
Shifting overwrites
values[i], so the original value waits in a local until its final position is known. -
What is the risk of writing
values[j + 1] = values[j]without a bound check?Answer
The loop reads before the start of the array
When
jreaches -1, the next read would index before the array, which is whyj >= 0is tested first.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev