Skip to content

Instantly share code, notes, and snippets.

@onsah
Created March 3, 2019 09:11
Show Gist options
  • Save onsah/072b79012b147441d7b06167d6fcaee2 to your computer and use it in GitHub Desktop.
Save onsah/072b79012b147441d7b06167d6fcaee2 to your computer and use it in GitHub Desktop.
struct Node {
Node() : next{0}, value{0}, head{true}
{ }
Node(int val, Node* next = 0) : next{next}, value{val}, head{false}
{ }
~Node() {
if (next)
delete next;
}
Node* pushNode(int val)
{
if (this->next)
delete next;
this->next = new Node(val);
return this->next;
}
void popNode()
{
if (this->next) {
Node* tmp = this->next->next;
this->next->next = 0;
delete this->next;
this->next = tmp;
}
}
Node* next;
int value;
bool head;
};
void countSort(int *arr, int size, int exp)
{
Node* heads[10];
Node* tails[10];
for (int i = 0; i < 10; ++i) {
heads[i] = new Node{};
tails[i] = heads[i];
}
for (int i = 0; i < size; ++i) {
int index = (arr[i] / exp) % 10;
// remainder can be negative
if (index < 0)
index += 10;
tails[index] = tails[index]->pushNode(arr[i]);
}
int current = 0;
for (int i = 0; i < 10; ++i) {
while (heads[i]->next) {
arr[current] = heads[i]->next->value;
current += 1;
heads[i]->popNode();
}
}
for (int i = 0; i < 10; ++i)
delete heads[i];
}
int max(int *arr, int size)
{
int max = arr[0];
for (int i = 1; i < size; ++i)
if (arr[i] > max)
max = arr[i];
return max;
}
void radixSort(int *arr, int size)
{
int maxVal = max(arr, size);
for (int exp = 1; (maxVal / exp) > 0; exp *= 10)
countSort(arr, size, exp);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment