Last active
September 26, 2022 22:08
-
-
Save RandyGaul/70bbeaf587c3bf14b737c8a9664ed62a to your computer and use it in GitHub Desktop.
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
#include <stdio.h> | |
#include <assert.h> | |
struct item_t | |
{ | |
int key; | |
int val; | |
}; | |
int get_byte(int val, int byte_index) | |
{ | |
return (val >> (8 * byte_index)) & 0xFF; | |
} | |
// Flip the sign bit so negative numbers aren't treating as ginormous. | |
int get_key(int val) | |
{ | |
return val ^ (1 << 31); | |
} | |
// O(N * k) sort where k is width of `int`. | |
// This is faster than O(N * Log(N)) since the sort predicate returns more | |
// than one bit of information, as opposed to e.g. < operator. | |
// Resource: https://hero.handmade.network/forums/code-discussion/t/984-day_229__what_about_radix_sort | |
void radix_sort(item_t* src, item_t* temp, int n) | |
{ | |
// Count all frequencies of each byte. | |
int counts[4][256] = { 0 }; | |
for (int i = 0; i < n; ++i) { | |
int key = get_key(src[i].key); | |
counts[0][get_byte(key, 0)]++; | |
counts[1][get_byte(key, 1)]++; | |
counts[2][get_byte(key, 2)]++; | |
counts[3][get_byte(key, 3)]++; | |
} | |
// Transform to prefix sum format. Shift elements to the right one index. | |
// This informs us of where the solution goes in the final answer. | |
for (int i = 0; i < 4; ++i) { | |
int total = 0; | |
for (int j = 0; j < 256; j++) { | |
int count = counts[i][j]; | |
counts[i][j] = total; | |
total += count; | |
} | |
} | |
// Fill in the solution based on the prefix array. | |
// Temp space is required for low branching and sort stability. | |
for (int i = 0; i < 4; ++i) { | |
for (int j = 0; j < n; j++) { | |
int key = get_key(src[j].key); | |
int byte = get_byte(key, i); | |
temp[counts[i][byte]++] = src[j]; | |
} | |
item_t* swap = src; | |
src = temp; | |
temp = swap; | |
} | |
} | |
int main() | |
{ | |
item_t in[] = { | |
{ 13, 0 }, | |
{ 5, 1 }, | |
{ 5, 2 }, | |
{ 3, 3 }, | |
{ 7, 4 }, | |
{ -3, 5 }, | |
{ -10, 6 }, | |
{ 1, 7 }, | |
{ 0, 8 }, | |
{ 2, 9 }, | |
}; | |
item_t temp[sizeof(in) / sizeof(in[0])]; | |
int n = sizeof(in) / sizeof(in[0]); | |
radix_sort(in, temp, n); | |
for (int i = 0; i < n; ++i) { | |
printf("{ %d, %d }\n", in[i].key, in[i].val); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment