#include <stdio.h>
#include <stdlib.h>
#ifdef __GNUC__
#define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
#define WARN_IF_UNUSED
#endif
struct node {
int v;
struct node *next;
};
struct linklist {
struct node *head;
struct node *tail;
};
WARN_IF_UNUSED int init(struct linklist ll[], int n) {
int i;
for (i = 0; i < n; ++i) {
ll[i].head = (struct node *)malloc(sizeof(struct node));
if (ll[i].head == NULL) {
return 0;
}
ll[i].head->next = NULL;
ll[i].tail = ll[i].head;
}
return 1;
}
void dump(struct linklist *ll) {
struct node *p = ll->head->next;
while (p != NULL) {
printf("%d ", p->v);
p = p->next;
}
printf("\n");
}
WARN_IF_UNUSED int push(struct linklist *ll, int v) {
struct node *p = (struct node *)malloc(sizeof(struct node));
if (p == NULL) {
return 0;
}
p->v = v;
p->next = NULL;
ll->tail->next = p;
ll->tail = p;
return 1;
}
int isEmpty(struct linklist *ll) {
return (ll->head->next == NULL) ? 1 : 0;
}
int pop(struct linklist *ll) {
if (isEmpty(ll)) {
exit(1);
}
struct node *p = ll->head;
ll->head = p->next;
free(p);
return ll->head->v;
}
void radixSort(int a[], int n) {
struct linklist ll[10];
int flag, i, j, t, fact = 1;
if (init(ll, 10) == 0) {
exit(2);
}
do {
printf("---------------\n");
flag = 0;
for (i = 0; i < n; ++i) {
t = a[i] / fact % 10;
flag += !!t;
//printf("%d: %d\n", a[i], t);
if (push(&ll[t], a[i]) == 0) {
exit(2);
}
}
for (i = 0, j = 0; i < 10; ++i) {
printf("%d: ", i);
dump(&ll[i]);
}
for (i = 0, j = 0; i < 10; ++i) {
while (isEmpty(&ll[i]) == 0) {
a[j] = pop(&ll[i]);
j++;
}
}
fact *= 10;
}while (flag != 0);
}
int main() {
int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
radixSort(a, N);
int i;
for (i = 0; i < N; ++i) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
#include <stdlib.h>
#ifdef __GNUC__
#define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
#define WARN_IF_UNUSED
#endif
struct node {
int v;
struct node *next;
};
struct linklist {
struct node *head;
struct node *tail;
};
WARN_IF_UNUSED int init(struct linklist ll[], int n) {
int i;
for (i = 0; i < n; ++i) {
ll[i].head = (struct node *)malloc(sizeof(struct node));
if (ll[i].head == NULL) {
return 0;
}
ll[i].head->next = NULL;
ll[i].tail = ll[i].head;
}
return 1;
}
void dump(struct linklist *ll) {
struct node *p = ll->head->next;
while (p != NULL) {
printf("%d ", p->v);
p = p->next;
}
printf("\n");
}
WARN_IF_UNUSED int push(struct linklist *ll, int v) {
struct node *p = (struct node *)malloc(sizeof(struct node));
if (p == NULL) {
return 0;
}
p->v = v;
p->next = NULL;
ll->tail->next = p;
ll->tail = p;
return 1;
}
int isEmpty(struct linklist *ll) {
return (ll->head->next == NULL) ? 1 : 0;
}
int pop(struct linklist *ll) {
if (isEmpty(ll)) {
exit(1);
}
struct node *p = ll->head;
ll->head = p->next;
free(p);
return ll->head->v;
}
void radixSort(int a[], int n) {
struct linklist ll[10];
int flag, i, j, t, fact = 1;
if (init(ll, 10) == 0) {
exit(2);
}
do {
printf("---------------\n");
flag = 0;
for (i = 0; i < n; ++i) {
t = a[i] / fact % 10;
flag += !!t;
//printf("%d: %d\n", a[i], t);
if (push(&ll[t], a[i]) == 0) {
exit(2);
}
}
for (i = 0, j = 0; i < 10; ++i) {
printf("%d: ", i);
dump(&ll[i]);
}
for (i = 0, j = 0; i < 10; ++i) {
while (isEmpty(&ll[i]) == 0) {
a[j] = pop(&ll[i]);
j++;
}
}
fact *= 10;
}while (flag != 0);
}
int main() {
int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
radixSort(a, N);
int i;
for (i = 0; i < N; ++i) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}






