#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_heap_primitives.h"

Include dependency graph for cgul_heap_sort.h:

This graph shows which files directly or indirectly include this file:

Functions
CGUL_BEGIN_C CGUL_EXPORT void	cgul_heap_sort (cgul_exception_t cex, void v, size_t v_count, size_t element_size, cgul_heap_primitives__compare_t cf)

CGUL_EXPORT void	cgul_heap_sort_pointers (cgul_exception_t cex, void *v, size_t v_count, cgul_heap_primitives__compare_t cf)

Detailed Description

Heap sort an array.

Author: Paul Serice

Function Documentation

§ cgul_heap_sort()

CGUL_BEGIN_C CGUL_EXPORT void cgul_heap_sort	(	cgul_exception_t *	cex,
		void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_heap_primitives__compare_t	cf
	)

Generic in-place sort with the same parameter signature as stdlib's qsort(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. cf is the comparison function. It will be passed pointers to two elements. It must return less than zero, zero, or greater than zero if the first element is less than, equal to, or greater than the second element. As explained in the next paragraph, this function has to internally allocate memory to perform its task. If out-of-memory occurs, an exception is thrown.

One of the main reasons for using heap sort is that it requires no extra space, but this function creates an extra copy of v and another array of pointers that gets passed to cgul_heap_sort_pointers(). So, if the reason for using heap sort is to conserve space, client code should be organized around arrays of pointers that can be passed directly to cgul_heap_sort_pointers().

If you need to constantly maintain a sorted list, cgul_rbtree or cgul_multimap are usually better solutions.

Parameters

[in,out]	cex	c-style exception
[in]	v	array of elements to sort
[in]	v_count	number of elements in `v`
[in]	element_size	size of each element in `v` (in bytes)
[in]	cf	comparison function

Referenced by cgul_heap_sort_cxx::sort().

§ cgul_heap_sort_pointers()

CGUL_EXPORT void cgul_heap_sort_pointers	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		cgul_heap_primitives__compare_t	cf
	)

If your array is already composed of pointers, you can directly call this function. v will be sorted using cf the same as described for cgul_heap_sort() except this function operates without using any extra space.