/** * 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. */ } }

Powered by GitList 1.0.1