insertion_sort.c

/* For reference see:
 * http://www.franken-business.de/galileo-computing/c-von-a-bis-z/022_c_algorithmen_003.htm#mj925248949647af9ef7f16d215f433a8c
 * http://www.algorithm-code.com/wiki/Insertion_sort#C_Code
 */
#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, x;

    for (i = 1; i < n; i++) {
        x = arr[i];

        for (j = i - 1; ((j >= 0) && (x < arr[j])); j--) {
            arr[j + 1] = arr[j];
        }

    arr[j + 1] = x;
    }
}


int main(void)
{
    int a1[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int a2[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int a3[9] = {2, 6, 6, 2, 5, 7, 9, 0, 3};
    int i;

    insertion_sort(a1, 9);
    insertion_sort(a2, 9);
    insertion_sort(a3, 9);

    for (i = 0; i < 9; i++) {
        printf("%i, ", a1[i]);
    }
    printf("\n");
    for (i = 0; i < 9; i++) {
        printf("%i, ", a2[i]);
    }
    printf("\n");
    for (i = 0; i < 9; i++) {
        printf("%i, ", a3[i]);
    }
    printf("\n");
}