nemea-common  1.6.3
Enumerations | Functions
counting_sort.h File Reference

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 *))
 

Detailed Description

Counting sort - A stable sorting algorithm which is not based on compare and exchange principle.

Author
Tomas Jansky jansk.nosp@m.y@ce.nosp@m.snet..nosp@m.cz
Date
2018

Definition in file counting_sort.h.

Enumeration Type Documentation

◆ cs_order

enum cs_order

Possible orders - ascending and descending.

Enumerator
CS_ORDER_ASC 
CS_ORDER_DSC 

Definition at line 53 of file counting_sort.h.

◆ cs_ret_code

Possible return codes of counting sort function.

Enumerator
CS_SUCCESS 

Success.

CS_BAD_PARAM 

Indicates wrong input parameter (NULL pointers, zero number of items, zero item size, minimal key >= maximal key value...

CS_MEMORY 

Indicates that internally used calloc function was unable to allocate memory.

CS_BAD_INDEX 

Indicates that one or more of keys does not fit into the specified range of possible key values.

Definition at line 61 of file counting_sort.h.

Function Documentation

◆ counting_sort()

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)

Parameters
[in]inputPointer to the first item of the array of items which need to be sorted.
[out]outputPointer to the array where should this function copy sorted items (must be at least same length as the input array!).
[in]countNumber of items to sort.
[in]sizeSize of each sorted item.
[in]key_minMinimal possible value of an item key.
[in]key_maxMaximal possible value of an item key.
[in]orderSpecified order in which the items should be sorted (CS_ORDER_ASC | CS_ORDER_DSC).
[in]get_keyPointer to a user-defined function which dereferences an item and returns its key.
Returns
CS_SUCCESS on success, error code otherwise (see details of cs_ret_code enum) and content of the output array is undefined