nemea-common
1.6.3
|
Counting sort - A stable sorting algorithm which is not based on compare and exchange principle. More...
#include <stdint.h>
Go to the source code of this file.
Enumerations | |
enum | cs_order { CS_ORDER_ASC = 0 , CS_ORDER_DSC } |
Possible orders - ascending and descending. More... | |
enum | cs_ret_code { CS_SUCCESS = 0 , CS_BAD_PARAM , CS_MEMORY , CS_BAD_INDEX } |
Possible return codes of counting sort function. More... | |
Functions | |
cs_ret_code | counting_sort (const void *input, void *output, uint32_t count, uint32_t size, uint32_t key_min, uint32_t key_max, cs_order order, uint32_t(*get_key)(const void *)) |
Counting sort - A stable sorting algorithm which is not based on compare and exchange principle.
Definition in file counting_sort.h.
enum cs_order |
Possible orders - ascending and descending.
Enumerator | |
---|---|
CS_ORDER_ASC | |
CS_ORDER_DSC |
Definition at line 53 of file counting_sort.h.
enum cs_ret_code |
Possible return codes of counting sort function.
Definition at line 61 of file counting_sort.h.
cs_ret_code counting_sort | ( | const void * | input, |
void * | output, | ||
uint32_t | count, | ||
uint32_t | size, | ||
uint32_t | key_min, | ||
uint32_t | key_max, | ||
cs_order | order, | ||
uint32_t(*)(const void *) | get_key | ||
) |
Counting sort. Sorts an array o N items with known range of possible values (keys) K. Only usable for items which keys are known to be in some limited range which is a small constant and not a linear function of the number of items. Does not (and by its nature can not) work for items with negative key values or for items with key values represented by a floating point number. Asymptotic time complexity: O(N + K) Outplace - exact space complexity: 2N + K Stable (two objects with equal keys appear in the same order in sorted output as they appear in the input array)
[in] | input | Pointer to the first item of the array of items which need to be sorted. |
[out] | output | Pointer to the array where should this function copy sorted items (must be at least same length as the input array!). |
[in] | count | Number of items to sort. |
[in] | size | Size of each sorted item. |
[in] | key_min | Minimal possible value of an item key. |
[in] | key_max | Maximal possible value of an item key. |
[in] | order | Specified order in which the items should be sorted (CS_ORDER_ASC | CS_ORDER_DSC). |
[in] | get_key | Pointer to a user-defined function which dereferences an item and returns its key. |