csortingpointerslinked-listcounting-sort

How do implement Count sort using linked list?


What I am trying to do is to create a counting sort using a linked list so I can link two similar elements in the same index and then copy from left to right to the original array. But my Buckets[i] are always NULL even after insertion. So my resulting array does not change. I don't know what I am doing wrong.

#include <stdio.h> 
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
} **Buckets;

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int findMax(int A[], int n) {
    int i, max = A[0];
    for (i = 0; i < n; i++) {
        if (A[i] > max)
            max = A[i];
    }
    return max;
}
void Insert(struct Node *p, int x) {
    while (p != NULL) {
        p = p->next;
    }
    Node *t = t = (struct Node *)malloc(sizeof(struct Node));
    t->data = x;
    t->next = NULL;
    p = t;
}

int Delete(struct Node *Buckets) {
    while (Buckets->next != NULL) {
        Buckets = Buckets->next;
    }
    int temp = Buckets->data;
    free(Buckets);
    return temp;
}

void BucketSort(int A[], int size) {
    int max, i, j;
    max = findMax(A, size);

    Buckets = new Node * [max + 1];
    for (i = 0; i < max + 1; i++) {
        Buckets[i] = NULL;
    }
    for (i = 0; i < size; i++) {
        Insert(Buckets[A[i]], A[i]); //insertion
    }
    i = j = 0;
    while (i < max + 1) {
        while (Buckets[i] != NULL) {
            A[j++] = Delete(Buckets[i]); // copy back in array
        }
        i++;
    }
}

int main() {
    int arr[] = { 3, 8, 5, 1, 10 };
    int size = sizeof(arr) / sizeof(arr[0]); //5
    printf("\nBefore : ");
    printArray(arr, size);

    BucketSort(arr, size);

    printf("\nAfter : ");
    printArray(arr, size);

    return 0;
}

Solution

  • Your Insert function doesn't really modify the list – you just assign the new node to a local variable, which goes out of scope immediately.

    You can solve this by passing a pointer to a node pointer to the function. That pointer points at the head pointer at first and at the next member of the preceding node when you advance:

    void Insert(struct Node **p, int x)
    {
        while (*p) p = &(*p)->next;
    
        *p = new Node(x);     // assume a c'tor here
    }
    

    Call the function like so:

    for (i = 0; i < size; i++) {
        Insert(&Buckets[A[i]] ,A[i]);
    }
    

    The same goes for deletion: You must modify the links or the list head when you delete:

    int Delete(struct Node **p)
    {
        int temp = (*p)->data;
        struct Node *del = *p;
    
        *p = (*p)->next;
    
        delete del;
        return temp;
    }
    

    (This code extracts the head node, which is probably what you want: You insert at the end, then retrieve from the beginning. That should preserve the original order. Not that it matters miuch in your case, where you have no data beside the int.)

    Call Delete like so:

    i = j = 0;
    while (i < max + 1) {
        while (Buckets[i]) {
            A[j++] = Delete(&Buckets[i]); 
        }
        i++;
    }