/**
* Copyright © 2016-2019 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.
*/
void array_sort(unsigned int **array, unsigned int count);
#define ARRAY_SORT 1
#include "common.c"
/*
* Implementation of insertion sort:
*/
void array_sort(unsigned int **array, unsigned int count) {
unsigned int *src; /* Unsorted, source array. */
unsigned int i; /* Index to iterate over the array. */
int j; /* Index for shifts and insertions. */
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];
/* 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;
++ insertions;
}
}
VERBOSE(1, " Insertion sort: made %u insertions, moved %u items.\n", insertions, moved_items);
}