C Insertion Sort
So I wanted to investigate different sorting algorithms for a few personal projects, and I thought while I was doing so that I would write little tutorials for each algo :) why not! First we have one of the most basic sorting algorithms, the Insertion Sort.
Explanation
As illustrated by this video, the insertion sort works much like you might sort a deck of cards laying infront of you on a table. For each value in a list, we compare the value with the previous value. If the current value is lesser than the previous, we move the current value backwards, repeating until considered greater than an already sorted value.
Implementation
First we need to include stdio.h for printf(), which is called in the dump() function below which simply prints the array contents to stdout.
#include <stdio.h>
#include <string.h>
void
dump(char *label, char **arr, int len) {
printf("%s:\n", label);
for (int i = 0; i < len; ++i) {
printf("%s ", arr[i]);
}
printf("\n\n");
}
Next on to insertionSort(). Here we accept a “pointer to a pointer” aka, a pointer array, and a len integer. We start our for loop at 1 because an array with a length of is already sorted. We assign key and then begin our backwards comparison, seeing if key is lesser than any previously sorted values.
void
insertionSort(char **arr, int len) {
for (int k = 1; k < len; ++k) {
char *key = arr[k];
int i = k - 1;
while (i >= 0 && strcmp(key, arr[i]) < 0) {
arr[i + 1] = arr[i--];
}
arr[i + 1] = key;
}
}
In our definition of main() we simply initialize 6 c strings and perform our insertion sort, dumping before and after the sort.
int
main(int argc, const char **argv){
char *arr[6] = { "1.0.0", "0.2.0", "2.0", "0.0.1", "0.5.0", "1.0.0beta" };
dump("before", arr, 6);
insertionSort(arr, 6);
dump("after", arr, 6);
return 0;
}
Compile
$ gcc insertionSort.c -std=c99 -o insertionSort
$ ./insertionSort
stdout:
before:
1.0.0 0.2.0 2.0 0.0.1 0.5.0 1.0.0beta
after:
0.0.1 0.2.0 0.5.0 1.0.0 1.0.0beta 2.0
