/**
* 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"
/* Threshold under which Sedgewick's recommendation feels overkill: */
#define TRIVIAL_ARRAY_THRESHOLD 5
/*
* Implementation of quick sort:
*/
void quick_sort(unsigned int *array, unsigned int start, unsigned int end) {
unsigned int count; /* Size of the array being treated. */
unsigned int a, b, c; /* Used for the median-of-three computation. */
unsigned int pivot_value; /* Value used to determine where to split. */
unsigned int i; /* Iterator from the start of the array to the pivot index. */
unsigned int j; /* Iterator from the end of the array to the pivot index. */
unsigned int swap; /* Used to swap values. */
if (start >= end) return;
count = end - start + 1;
/* Pick a pivot value: */
if (count < TRIVIAL_ARRAY_THRESHOLD) {
/* Do not bother for really trivial arrays: */
pivot_value = array[start];
}
else {
/* Otherwise, follow Sedgewick's recommendation of choosing the median
of the first, middle and last element of the array: */
a = array[start]; b = array[start + (count / 2)]; c = array[end];
if ((a >= b && a <= c) || (a >= c && a <= b)) {
pivot_value = a;
}
else if ((b >= a && b <= c) || (b >= c && b <= a)) {
pivot_value = b;
}
else {
pivot_value = c;
}
}
/* Determine where to split the array, following Hoare's partition scheme: */
i = start - 1;
j = end + 1;
while (1) {
do { ++ i; } while (array[i] < pivot_value);
/* array[i] is now larger than or equal to pivot_value despite being on
the left side of the pivot. */
do { -- j; } while (array[j] > pivot_value);
/* array[j] is now less than or equal to pivot_value despite being on
the right side of the pivot. */
if (i >= j) {
/* i and j passed each other: it is time to split the array at index j: */
break;
}
/* Swap array[i] and array[j] to respect the pivot: */
swap = array[i];
array[i] = array[j];
array[j] = swap;
}
/* Sort the sub-arrays on each side of the pivot: */
quick_sort(array, start, j);
quick_sort(array, j + 1, end);
}
void array_sort(unsigned int **array, unsigned int count) {
/* Do nothing unless there are at least two items to sort: */
if (count < 2) return;
/* Quick sort is an in-place algorithm, i.e. we work directly on the
provided array: */
quick_sort(*array, 0, count - 1);
}