cdata-structureslinked-listradix-sort

Radix sort a linked list - linking the buckets


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("%dA\n",i);
            if (bucket[i] != NULL)
            {
                //printf("%dB\n",i);
                if (*head == NULL)
                {
                    *head = bucket[i];
                   // printf("%dC\n",i);
                }
                else
                {
                    //printf("%dD\n",i);
                    tail[9 - i]->next = bucket[i];
                    //printf("%dF\n",i);
                }

               // tail[9 - i] = tail[i];
            }
            else{
               // printf("%dE\n",i);
            }
    //printf("here\n");
        }
    }
}

// Function to create a new node with the given key and value
Node *createNode(int key, const char *value)
{
    Node *node = (Node*) malloc(sizeof(Node));
    node->key = key;
    strcpy(node->value, value);
    node->next = NULL;
    return node;
}

// Function to append a new node with the given key and value to the end of the list
Node *append(Node *head, int key, const char *value)
{
    Node *newNode = createNode(key, value);
    Node *curr = head;
    if (head == NULL)
    {
        return newNode;
    }
    while (curr->next != NULL)
    {
        curr = curr->next;
    }
    curr->next = newNode;
    return head;
}

// Function to print the linked list
void printList(Node *head)
{
    Node *curr = head;
    while (curr != NULL)
    {
        printf("(%d, %s) ", curr->key, curr->value);
        curr = curr->next;
    }
    printf("\n");
}

The segmentation fault occurs when tail[9 - i]->next = bucket[i]; is executed.

I added printf statements (turned them into comment blocks) to trace where the error is. Can someone please help me figure out a way to get this to work?


Solution

  • There are a few issues:

    Here is the corrected factor loop code -- comments indicate where corrections were made:

        for (factor = 1; maxDigits > 0; factor *= 10, maxDigits--)
        {
            memset(digits, 0, sizeof(digits)); // reset!
            memset(bucket, 0, sizeof(bucket)); // reset!
            
            curr = *head;
            while (curr != NULL)
            {
                digits[curr->key / factor % 10]++;
                curr = curr->next;
            }
            
            for (i = 1; i < 10; i++)
            {
                digits[i] += digits[i - 1];
            }
    
            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;
            }
    
            *head = NULL;
            curr = NULL; // <-- track the current tail of the newly built list
            for (i = 9; i >= 0; i--)
            {
                if (bucket[i] != NULL)
                {
                    if (*head == NULL)
                    {
                        *head = bucket[i];
                    }
                    else
                    {
                        curr->next = bucket[i]; // Append bucket after the current tail
                    }
                    curr = tail[i]; // The tail is now at the end of this bucket
                }
            }
            curr->next = NULL; // Terminate the list properly
        }