/**
* 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"
#define heap_parent_index(x) (((x) - 1) / 2)
#define heap_lchild_index(x) ((2 * (x)) + 1)
#define heap_rchild_index(x) ((2 * (x)) + 2)
void sift_down(unsigned int *heap, unsigned int start, unsigned int end) {
unsigned int root; /* Root of the heap being inspected. */
unsigned int child; /* Child of the heap being inspected. */
unsigned int swap; /* Node to be swapped with the root. */
unsigned int swap_node; /* Used for the actual swap operation. */
VERBOSE(3, " sift_down(heap, %u, %u)\n", start, end);
/* We want to sift down the provided heap, so we start at its root and
explore down, looking for anomalies, i.e. for children larger than their
parent node. */
root = start;
/* While the root being inspected has at least one child: */
while ((child = heap_lchild_index(root)) <= end) {
/* By default, we consider everything is fine, nothing needs to be
swapped: */
swap = root;
/* Check the left child: */
if (heap[child] > heap[root]) {
/* The left child is larger than the root, it is candidate to be
swapped with the root: */
swap = child;
}
/* Check the right child (if any) against either its sibling
or the root: */
if (child + 1 <= end && heap[child + 1] > heap[swap]) {
swap = child + 1;
}
/* Proceed with the swapping, if necessary: */
if (swap == root) {
return;
}
else {
swap_node = heap[swap];
heap[swap] = heap[root];
heap[root] = swap_node;
/* Consider the node we swapped as the new root and keep looping: */
root = swap;
}
}
}
/*
* Implementation of heap sort:
*/
void array_sort(unsigned int **array, unsigned int count) {
unsigned int *src; /* Unsorted, source array. */
unsigned int swap; /* Used to swap values. */
int heap_end; /* End of our heap. */
int i; /* Used to iterate over the array. */
/* Do nothing unless there are at least two items to sort: */
if (count < 2) return;
/* Heap sort is an in-place algorithm, i.e. we work directly on the
provided array: */
src = *array;
heap_end = count - 1;
/* The first step consists in turning the array into a max heap (i.e. into
a binary tree with the maximum value at the top). */
for (i = heap_parent_index(heap_end); i >= 0; --i) {
sift_down(src, i, heap_end);
}
while (heap_end > 0) {
/* The second step consists in swapping the root of our max heap (i.e.
the largest value in the whole array) with the last item: */
swap = src[heap_end];
src[heap_end] = src[0];
src[0] = swap;
/* The third step consists in fixing our now-smaller but disturbed max
heap by calling sift_down() again: */
sift_down(src, 0, -- heap_end);
/* Next, we loop until our heap has but a single value. */
}
}