remainder

sort.c

// GistID: 6172227
#include <stdio.h>
#include <stdlib.h>

struct node_t {
    struct node_t *next;
    int val;
};

typedef struct node_t node;

typedef struct {
    node *head;
    node *tail;
} list;

list* new_list()
{
    list* l = (list*)malloc(sizeof(list));
    l->head = NULL;
    l->tail = NULL;
    return l;
}

void destroy_list(list* l)
{
    node* head = l->head;
    node* p;
    while (head) {
        p = head->next;
        free(head);
        head = p;
    }
    free(l);
}

void insert(list* l, int val) {
    node* n = (node*)malloc(sizeof(node));
    n->val = val;
    // warning: n->next = NULL;
    if (!l->head) {
        l->head = n;
        l->tail = n;
    } else {
        l->tail->next = n;
        l->tail = n;
    }
}

void sort(int a[], int size)
{
    const int n = 10;
    int i = 0;
    list* remainder[n];
    list* quotient[n];
    node* nd;
    int index = 0;
    for (i = 0; i < n; i++) {
        remainder[i] = new_list();
        quotient[i] = new_list();
    }
    for (i = 0; i < size; i++) {
        insert(remainder[a[i]%n], a[i]);
    }
    for (i = 0; i < n; i++) {
        nd = remainder[i]->head;
        while (nd) {
            insert(quotient[nd->val/n], nd->val);
            nd = nd->next;
        }
    }
    for (i = 0; i < n; i++) {
        nd = quotient[i]->head;
        while (nd) {
            a[index++] = nd->val;
            nd = nd->next;
        }
    }
    for (i = 0; i < n; i++) {
        destroy_list(remainder[i]);
        destroy_list(quotient[i]);
    }
}

int main(int argc, char *argv[])
{
    #define SIZE 20
    int arr[SIZE] = {5,15,10,20,6,
                 16,11,27,32,98,
                 82,76,25,1,23,
                 28,73,27,21,19};
    int i = 0;
    sort(arr, SIZE);
    for (i = 0; i < SIZE; i++) {
        printf("%d,", arr[i]);
    }
    printf("\n");
    return 0;
}