I'm trying to implement radix sort on a linked list based on an integer with the code below.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DIGITS 10 // maximum number of digits in a key
// Structure for a node in the linked list
typedef struct node
{
int key; // the key to be sorted
char value[20]; // the value associated with the key
struct node *next; // pointer to the next node in the list
} Node;
// Function prototypes
void radixSort(Node **head);
Node *createNode(int key, const char *value);
Node *append(Node *head, int key, const char *value);
void printList(Node *head);
int main(void)
{
Node *head = NULL; // head of the linked list
// Create a linked list with some random keys and values
head = append(head, 456, "apple");
head = append(head, 345, "banana");
head = append(head, 123, "cherry");
head = append(head, 789, "date");
head = append(head, 231, "elderberry");
head = append(head, 567, "fig");
head = append(head, 876, "grape");
// Print the original list
printf("Original list:\n");
printList(head);
// Sort the list using radix sort
radixSort(&head);
// Print the sorted list
printf("Sorted list:\n");
printList(head);
return 0;
}
// Function to sort the linked list using radix sort
void radixSort(Node **head)
{
Node *bucket[10]; // array of buckets
Node *curr; // pointer to the current node
Node *tail[10]; // array of tails for each bucket
int i, j, k;
int factor; // factor to sort on
int digits[MAX_DIGITS]; // array to store the digits of the keys
// Initialize the buckets and tails
for (i = 0; i < 10; i )
{
bucket[i] = NULL;
tail[i] = NULL;
}
// Find the maximum number of digits in the keys
int maxDigits = 0;
curr = *head;
while (curr != NULL)
{
int key = curr->key;
int numDigits = 0;
while (key > 0)
{
numDigits ;
key /= 10;
}
if (numDigits > maxDigits)
{
maxDigits = numDigits;
}
curr = curr->next;
}
// Loop through each digit, starting with the least significant digit
for (factor = 1; maxDigits > 0; factor *= 10, maxDigits--)
{
// Extract the digits of the keys
curr = *head;
while (curr != NULL)
{
digits[curr->key / factor % 10] ;
curr = curr->next;
}
// Cumulative sum of the digits
for (i = 1; i < 10; i )
{
digits[i] = digits[i - 1];
}
// Sort the nodes into the appropriate buckets
curr = *head;
while (curr != NULL)
{
int digit = curr->key / factor % 10;
if (bucket[digit] == NULL)
{
bucket[digit] = curr;
tail[digit] = curr;
}
else
{
tail[digit]->next = curr;
tail[digit] = curr;
}
curr = curr->next;
}
// Rebuild the list in sorted order
*head = NULL;
for (i = 9; i >= 0; i--)
{
//printf("