Last active
May 15, 2024 15:40
-
-
Save pankkor/e6bea3d5279730a6826748ca647da7c5 to your computer and use it in GitHub Desktop.
Counting sort algorithm (https://en.m.wikipedia.org/wiki/Counting_sort)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Counting sort algorithm | |
// https://en.m.wikipedia.org/wiki/Counting_sort | |
// | |
// Build clang: | |
// clang -Wall -Wextra -Wpedantic -g counting_sort.c -o counting_sort | |
// | |
// Build gcc: | |
// gcc -Wall -Wextra -Wpedantic -g counting_sort.c -o counting_sort | |
typedef int i32; | |
#define LIKELY(x) __builtin_expect((x), 1) | |
#define UNLIKELY(x) __builtin_expect((x), 0) | |
// Debug and Release assert | |
static inline void assert_msg(i32 condition, const char *msg) { | |
if (UNLIKELY(!condition)) { | |
__builtin_printf("%s\n", msg); | |
// __debugbreak and __builtin_debugtrap() would allow SIGTRAPping into a debugger | |
// __builtin_trap generates SIGILL and code after it will be optmized away. | |
#if defined(_MSC_VER) | |
__debugbreak(); | |
#elif defined(__clang__) | |
__builtin_debugtrap(); | |
#else | |
__builtin_trap(); // gcc doesn't have __builtin_debugtrap equivalent | |
#endif | |
} | |
} | |
#define STR1(s) # s | |
#define STR(s) STR1(s) | |
#define ASSERT(condition) assert_msg(!!(condition), \ | |
__FILE__ ":" STR(__LINE__) ": (" STR(condition) ") expected to be true\n") | |
// Sort array of i32 using counting sort algorithm in ascending order. | |
// https://en.m.wikipedia.org/wiki/Counting_sort | |
// Best suited for arrays wich values range is smaller than element count N. | |
// Uses `index_size` memory for index. | |
// in_out_array - array to sort. | |
// in_out_index - auxiliary array to keep index for sorting. Will be zeroed out | |
// before sorting. | |
// [value_min, value_max) - range of values in the array. | |
// value_min - minimum value of an array | |
// value_max - maximum value of an array is calculated as | |
// (value_min + index_size) | |
void sort_counting_i32(i32 *in_out_arr, i32 arr_size, i32 *in_out_index, i32 index_size, | |
i32 arr_value_min) { | |
if (LIKELY(arr_size > 0 || index_size > 0 || in_out_arr || in_out_index)) | |
{ | |
// Count frequenices of values in the array | |
i32 arr_value_max = arr_value_min + index_size; | |
for (i32 i = 0; i < index_size; ++i) { | |
in_out_index[i] = 0; | |
} | |
for (i32 i = 0; i < arr_size; ++i) { | |
i32 v = in_out_arr[i]; | |
i32 index_i = v - arr_value_min; | |
ASSERT(index_i >= 0); | |
ASSERT(index_i < index_size); | |
++in_out_index[index_i]; | |
} | |
// Traditional implementation first makes cummulative frequency index | |
// (freq(N+1) = freq(N) + freq(N+1). Then it iterates backwards | |
// over array, decrementing frequency in frequency index for the | |
// value at array[i]. | |
// This implementation just goes straight over the index. | |
// It could be less efficient in case index is much larget than array. | |
i32 arr_i = 0; | |
for (i32 index_i = 0; index_i < index_size; ++index_i) { | |
i32 freq = in_out_index[index_i]; | |
for (i32 i = 0; i < freq; ++i) { | |
in_out_arr[arr_i++] = index_i + arr_value_min; | |
} | |
} | |
} | |
} | |
// Test | |
i32 is_equal_arrs_i32(i32 *a, i32 *b, i32 size) { | |
for (i32 i = 0; i < size; ++i) { | |
if (a[i] != b[i]) | |
{ | |
return 0; | |
} | |
} | |
return 1; | |
} | |
int main(void) { | |
{ | |
sort_counting_i32(0, 0, 0, 0, 0); | |
} | |
{ | |
i32 arr[] = { 10 }; | |
i32 arr_size = sizeof(arr) / sizeof(arr[0]); | |
enum { INDEX_SIZE = 1 }; | |
i32 index[INDEX_SIZE] = {0}; | |
sort_counting_i32(arr, arr_size, index, INDEX_SIZE, 10); | |
i32 expected_arr[] = {10}; | |
ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size)); | |
} | |
{ | |
i32 arr[] = { 0, 1, 2, 3 }; | |
i32 arr_size = sizeof(arr) / sizeof(arr[0]); | |
enum { INDEX_SIZE = 4 }; | |
i32 index[INDEX_SIZE] = {0}; | |
sort_counting_i32(arr, arr_size, index, INDEX_SIZE, 0); | |
i32 expected_arr[] = {0, 1, 2, 3}; | |
ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size)); | |
} | |
{ | |
i32 arr[] = { 3, 2, 1, 0, -1, -2, -3 }; | |
i32 arr_size = sizeof(arr) / sizeof(arr[0]); | |
enum { INDEX_SIZE = 7 }; | |
i32 index[INDEX_SIZE] = {0}; | |
sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -3); | |
i32 expected_arr[] = {-3, -2, -1, 0, 1, 2, 3}; | |
ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size)); | |
} | |
{ | |
i32 arr[] = { 30, 2, 1, 0, -1, -2, -30 }; | |
i32 arr_size = sizeof(arr) / sizeof(arr[0]); | |
enum { INDEX_SIZE = 61 }; | |
i32 index[INDEX_SIZE] = {0}; | |
sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -30); | |
i32 expected_arr[] = {-30, -2, -1, 0, 1, 2, 30}; | |
ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size)); | |
} | |
{ | |
i32 arr[] = { 30, 30, 2, 1, 0, 0, -1, -2, -2, -2, -2, -30, -30 }; | |
i32 arr_size = sizeof(arr) / sizeof(arr[0]); | |
enum { INDEX_SIZE = 61 }; | |
i32 index[INDEX_SIZE] = {0}; | |
sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -30); | |
i32 expected_arr[] = {-30, -30, -2, -2, -2, -2, -1, 0, 0, 1, 2, 30, 30}; | |
ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size)); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment