kindwolf.org Git repositories
master

## insertion-sort.c @master — raw · history · blame

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47``` ```/** * Copyright © 2016-2019 Xavier G. * 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); } ```