1 /*
  2  * radixSortLSD.c
  3  * Implement radix sort of Least Significant Digit
  4  *
  5  *  Created on: 2017年5月23日
  6  *      Author: ygh
  7  */
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 
 11 #define  MAX_LENGTH 10000
 12 
 13 /*
 14  *The quantity of the the keys of element
 15  *For example 0-9999 have four keys
 16  */
 17 #define MAX_DIGIT 6
 18 /*
 19  *The quantity of the bucket.In this case ,we sort integer number
 20  *So the buckets is from 0 to 9
 21  */
 22 #define RADIX 10
 23 
 24 #define BEGIN_DIGIT 0
 25 
 26 /*
 27  * The type of the element type
 28  */
 29 typedef int elementType;
 30 
 31 /*
 32  * Define a data structure for bucket node
 33  */
 34 typedef struct node *ptrToNode;
 35 typedef struct node {
 36     /*
 37      * The element type the bucket node store
 38      */
 39     elementType key;
 40     /*
 41      * A next point to point next element
 42      */
 43     ptrToNode next;
 44 
 45 };
 46 
 47 /*
 48  * Define a data structure for bucket head that
 49  * store the head point and rear point for the elements
 50  */
 51 typedef struct headNode {
 52     ptrToNode head, rear;
 53 };
 54 
 55 /*
 56  * Define a array of headNode to store the all buckets
 57  */
 58 typedef struct headNode bucket[RADIX];
 59 
 60 /*
 61  * Get the digit by the current number and current needed digit
 62  * @param x The current number
 63  * @param d The current digit
 64  * @return The digit needed
 65  */
 66 int getDigit(elementType x, int d) {
 67     int i;
 68     int di;
 69     for (i = 0; i < d; i++) {
 70         di = x % RADIX;
 71         x = x / RADIX;
 72     }
 73     return di;
 74 }
 75 
 76 void LSDRadixSort(elementType a[], int n) {
 77     int d, di, i;
 78     /*
 79      * Define a bucket array to store all buckets
 80      */
 81     bucket b;
 82 
 83     /*
 84      * Define three node point
 85      * @param temp Store temporary node
 86      * @param p A node point will be used when search
 87      * @param list A node point to build elements list and recovery
 88      * elements from finished sort
 89      */
 90     ptrToNode temp, p, list;
 91 
 92     /*
 93      * Initialize each bucket head and rear into NULL
 94      */
 95     for (i = BEGIN_DIGIT; i < RADIX; i++) {
 96         b[i].head = b[i].rear = NULL;
 97     }
 98 
 99     /*
100      * Change array elements into list elements,but it is DESC
101      */
102     for (i = 0; i < n; i++) {
103         temp = (ptrToNode) malloc(sizeof(struct node));
104         temp->key = a[i];
105         temp->next = list;
106         list = temp;
107     }
108 
109     /*
110      * Do radix sort
111      */
112     for (d = 1; d <= MAX_DIGIT; d++) {
113         p = list;
114         while (p) {
115             di = getDigit(p->key, d);
116             if (p->key < 0) {
117                 di = di * (-1);
118             }
119             /*
120              * Delete this element from the list
121              */
122             temp = p;
123             p = p->next;
124             temp->next = NULL;
125             if (b[di].head == NULL) {
126                 b[di].head = b[di].rear = temp;
127             } else {
128                 b[di].rear->next = temp;
129                 b[di].rear = temp;
130             }
131         }
132 
133         /*
134          * Recover the elements has been deal with,using
135          * the list to point the head
136          */
137         list = NULL;
138         for (di = RADIX - 1; di >= BEGIN_DIGIT; di--) {
139             if (b[di].head) {
140                 b[di].rear->next = list;
141                 list = b[di].head;
142                 /*
143                  * Clear the head and rear
144                  */
145                 b[di].rear = b[di].head = NULL;
146             }
147         }
148     }
149 
150     /*
151      * Put sorted list data to array
152      */
153     for (i = 0; i < n; i++) {
154         temp = list;
155         list = list->next;
156         a[i] = temp->key;
157         free(temp);
158     }
159 
160 }
161 
162 /*
163  * Print the array to console
164  * @param a A integer array need to sort
165  * @param n The length of the array
166  */
167 void printArray(int a[], int n) {
168     int i;
169     for (i = 0; i < n; i++) {
170         if (i == n - 1) {
171             printf("%d", a[i]);
172         } else {
173             printf("%d ", a[i]);
174         }
175     }
176     printf("\n");
177 }
178 
179 /*
180  * Get input data from command
181  */
182 void getInputData(elementType *a, int n) {
183     int i;
184     elementType x;
185     for (i = 0; i < n; i++) {
186         scanf("%d", &x);
187         a[i] = x;
188     }
189 }
190 
191 /*
192  * Separate a array into positive array and negative array
193  * @param a A array store the positive number or negative number
194  * @param n The length of the a
195  * @param pL The length of the positive array
196  * @param pL The length of the negative array
197  */
198 void separate(elementType *a, int n, int *pL, int *nL, elementType positiveArr[],
199         elementType negativeArr[]) {
200     int i;
201     for (i = 0; i < n; i++) {
202         if (a[i] < 0) {
203             negativeArr[(*nL)++] = a[i];
204         } else {
205             positiveArr[(*pL)++] = a[i];
206         }
207     }
208 }
209 
210 void radixSort(elementType a[], int n) {
211     int positiveArr[MAX_LENGTH];
212     int negativeArr[MAX_LENGTH];
213     int pL = 0, nL = 0, i, j;
214     separate(a, n, &pL, &nL, positiveArr, negativeArr);
215     LSDRadixSort(positiveArr, pL);
216     LSDRadixSort(negativeArr, nL);
217     i = nL - 1;
218     j = 0;
219     while (i >= 0) {
220         a[j] = negativeArr[i];
221         i--;
222         j++;
223     }
224     i = 0;
225     while (i < pL) {
226         a[j] = positiveArr[i];
227         i++;
228         j++;
229     }
230 
231 }
232 
233 int main() {
234     elementType a[MAX_LENGTH];
235     int n;
236     scanf("%d", &n);
237     getInputData(a, n);
238     radixSort(a, n);
239     printArray(a, n);
240     return 0;
241 }