#ifndef LIB_HEAPSORT_H_ #define LIB_HEAPSORT_H_ /* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/heapsort.h * \brief heapsort algorithm. * \ingroup lib * * Sort an array of randomed value using a virtual heap (it does not create * an real heap in the memory). * * see the heapsort page on wikipedia * http://en.wikipedia.org/wiki/Heapsort * * Complexity : O (n log n) * Mem : O (1) * * Some MACROS must be defined to use the heapsort. * * LIB_HEAPSORT_USER_TYPE corresponding to the type the lib heapsort will use * to sort the array * * LIB_HEAPSORT_USER_COMP user function to compare two values. * LIB_HEAPSORT_USER_SWAP user function swap to exchange two values. * * LIB_HEAPSORT_USER_PREFIX user prefix function. */ /** Verify if the MACROS had been defined. */ #if (!defined (LIB_HEAPSORT_USER_TYPE) \ || !defined (LIB_HEAPSORT_USER_COMP_LESSER) \ || !defined (LIB_HEAPSORT_USER_SWAP) \ || !defined (LIB_HEAPSORT_USER_PREFIX)) #error "Some macros had not been defined" #endif #define lib_heapsort_siftdown PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _siftdown) #define lib_heapsort_heapify PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _heapify) #define lib_heapsort PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _heapsort) /** * siftdown the heap. * * \param user_type the user type to do the siftdown on * \param start the start position * \param end the end position */ void lib_heapsort_siftdown (LIB_HEAPSORT_USER_TYPE *user_type, uint start, uint end) { uint root; uint child; dbg_assert (user_type); root = start; while ((child = root * 2 + 1) <= end) { if (child < end && LIB_HEAPSORT_USER_COMP_LESSER (user_type, child, child + 1)) { child ++; } if (LIB_HEAPSORT_USER_COMP_LESSER (user_type, root, child)) { LIB_HEAPSORT_USER_SWAP (user_type, root, child); root = child; } else { break; } } } /** * heapify, the user_type to sort * * \param user_type to sort * \param nb the number of data in the type */ void lib_heapsort_heapify (LIB_HEAPSORT_USER_TYPE *user_type, uint nb) { int start; dbg_assert (user_type); start = nb / 2 - 1; while (start >= 0) { lib_heapsort_siftdown (user_type, start, nb - 1); start --; } } /** * heapsort algorithm * * \param user_type the data to sort * \param nb the number of data in the type */ void lib_heapsort (LIB_HEAPSORT_USER_TYPE *user_type, uint nb) { dbg_assert (user_type); /* Do no sort empty table. */ if (nb == 0) return; uint end; lib_heapsort_heapify (user_type, nb); end = nb - 1; while (end) { LIB_HEAPSORT_USER_SWAP (user_type, 0, end); end --; lib_heapsort_siftdown (user_type, 0, end); } } #endif /*LIB_HEAPSORT_H_*/