Home > other >  Radix sort a linked list - linking the buckets
Radix sort a linked list - linking the buckets

Time:12-21

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("           
  • Related