insertion-sort.c
52ae979f
 /**
  * Copyright © 2016 Xavier G. <xavier@kindwolf.org>
  * This work is free. You can redistribute it and/or modify it under the
  * terms of the Do What The Fuck You Want To Public License, Version 2,
  * as published by Sam Hocevar. See the COPYING file for more details.
  */
 
0fc9a6f7
 void array_sort(unsigned int **array, unsigned int count);
 #define ARRAY_SORT 1
 #include "common.c"
 
52ae979f
 /*
  * Implementation of insertion sort:
  */
 void array_sort(unsigned int **array, unsigned int count) {
 	unsigned int *src;             /* Unsorted, source array. */
ead716a9
 	unsigned int i;                /* Index to iterate over the array. */
 	int j;                         /* Index for shifts and insertions. */
52ae979f
 	unsigned int register value;   /* Value being repositioned. */
 	unsigned int insertions;       /* Stats: # of insertions. */
 	unsigned int moved_items;      /* Stats: # of moved items. */
 
 	/* Do nothing unless there are at least two items to sort: */
 	if (count < 2) return;
 
 	/* Insertion-sort is an in-place algorithm, i.e. we work directly on the
 	provided array: */
 	src = *array;
 
 	insertions = 0;
 	moved_items = 0;
 	for (i = 1; i < count; ++ i) {
 		value = src[i];
ead716a9
 		/* Look back for the position where src[i] ought to be inserted,
 		shifting items on the way: */
 		for (j = i - 1; j >= 0 && src[j] > value; -- j) {
 			src[j + 1] = src[j];
 			++ moved_items;
 		}
 		/* If needed, insert src[i] to its new, correct position: */
 		if (j + 1 != i) {
 			src[j + 1] = value;
52ae979f
 			++ insertions;
 		}
 	}
9f7e168b
 	VERBOSE(1, "  Insertion sort: made %u insertions, moved %u items.\n", insertions, moved_items);
52ae979f
 }