Over on Stack Overflow, I read an answer asserting that Insertion Sort was inferior to Selection Sort for array data (as opposed to linked list data) on account of the larger amount of data movement that insertion sort performs on average. This claim was new to me, running counter to many assertions I have read and accepted over the years of the general superiority of Insertion sort among its comparison-sort peers. Moreover, my own algorithmic analysis supports Insertion sort as being slightly better on average for random data, assuming efficient implementations of both algorithms and an environment where memory writes are not appreciably more expensive than reads.
But inasmuch as the two algorithms have the same asymptotic cost, all the argumentation is so much smoke without testing. Therefore, I wrote a selection sort, an insertion sort, and a test harness to put some actual data in play. I was surprised by the results: my Insertion sort was way faster than my Selection sort on random input (about one fourth the running time), and Insertion was a clear winner even for its worst case of reverse-sorted input. I didn't expect Insertion to perform so much better in the average case, and I didn't expect it to win at all in the reverse-sorted input case.
And that brings me here. I present my two sort functions and the test harness for your review and commentary. I am particularly interested in insights on how the selection sort's performance might be improved, so as to ensure that the test is a fair one. I am also interested in commentary on any flaws in the test harness that might bias the results.
selection.c
void selection(int data[], unsigned int count) {
for (unsigned int i = 0; i < count - 1; i++) {
int min_value = data[i];
unsigned int min_index = i;
for (unsigned int j = i + 1; j < count; j++) {
if (data[j] < min_value) {
min_index = j;
min_value = data[j];
}
}
data[min_index] = data[i];
data[i] = min_value;
}
}
selection.h
void selection(int data[], unsigned int count);
insertion.c
void insertion(int data[], unsigned int count) {
for (unsigned int i = 1; i < count; i++) {
int test_value = data[i];
unsigned int j;
for (j = i; j > 0; j--) {
if (data[j - 1] > test_value) {
data[j] = data[j - 1];
} else {
break;
}
}
if (j != i) {
data[j] = test_value;
}
}
}
insertion.h
void insertion(int data[], unsigned int count);
main.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "insertion.h"
#include "selection.h"
#define NUM_ITEMS 16384
#define RANDOM_SEED 17231
#define ITERATIONS 32
#define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)
int original_items[NUM_ITEMS];
int selection_items[NUM_ITEMS];
int insertion_items[NUM_ITEMS];
int main(void) {
clock_t start_time;
clock_t total_time;
int num_distinct;
srand(RANDOM_SEED);
for (int i = 0; i < NUM_ITEMS; i++) {
original_items[i] = rand() % NUM_ITEMS;
}
// test selection
total_time = 0;
for (int i = 0; i < ITERATIONS; i++) {
memcpy(selection_items, original_items, sizeof(original_items));
start_time = clock();
selection(selection_items, NUM_ITEMS);
total_time += clock() - start_time;
}
// Validation / sanity check
num_distinct = 1;
for (int i = 1; i < NUM_ITEMS; i++) {
if (selection_items[i] < selection_items[i - 1]) {
printf("Selection result validation failed.\n");
}
if (selection_items[i] != selection_items[i - 1]) {
num_distinct++;
}
}
printf("%d distinct values sorted\n", num_distinct);
printf("Selection sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));
// test insertion
total_time = 0;
for (int i = 0; i < ITERATIONS; i++) {
memcpy(insertion_items, original_items, sizeof(original_items));
start_time = clock();
insertion(insertion_items, NUM_ITEMS);
total_time += clock() - start_time;
}
// Validation
for (int i = 0; i < NUM_ITEMS; i++) {
if (insertion_items[i] != selection_items[i]) {
printf("Insertion result differs from selection result.\n");
}
}
printf("Insertion sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));
}
Makefile
PROG = sort_test
OBJS = main.o selection.o insertion.o
CFLAGS = -O3 -Wall -Wextra -pedantic -std=c11
$(PROG) : $(OBJS)
$(CC) -o $@ $(CFLAGS) $(LDFLAGS) $^
main.o selection.o: selection.h
main.o insertion.o: insertion.h
clean:
rm $(PROG) $(OBJS)
.PHONY: clean
I built and tested the code in a WSL container running SUSE Leap 42.3, featuring GCC 4.8.5.
