The Radix Sort in C programming

The Radix Sort

The radix sort shown in Listing III.2c takes a list of integers and puts each element on a smaller list, depending
on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for
each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints, but it is illustrated here using strings. You can compile this example into a working program using the code at the end of this chapter.

Two functions perform the radix sort. The function radixSort() performs one pass through the data, performing a partial sort. Line 12 ensures that all the lists in table are empty. The loop on lines 13–24 executes as long as there is something on the input list. Lines 15–22 select which position in the table to put the next string on, based on the value of the character in the string specified by whichByte. If the string has fewer characters than whichByte calls for, the position is 0 (which ensures that the string “an” comes befor the string “and”). Finally, lines 25 and 26 concatenate all the elements of table into one big list in table[0]. The function sortStrings() sorts an array of strings by calling radixSort() several times to perform partial

sorts. Lines 39–46 create the original list of strings, keeping track of the length of the longest string (because
that’s how many times it needs to call radixSort()). Lines 47 and 48 call radixSort() for each byte in the
longest string in the list. Finally, lines 49 and 50 put all the strings in the sorted list back into the array. Note
that sortStrings() doesn’t free all the memory it allocatesj

An implementation of a radix sort.

1: #include <stdlib.h>
2: #include <limits.h>
3: #include <memory.h>
4: #include “list.h”
5:
6: /* Partially sort list using radix sort */
7: static list_t radixSort(list_t in, int whichByte)
8: {
9: int i;
10: list_t table[UCHAR_MAX + 1];
11:
12: memset(table, 0, sizeof(table));
13: while (in.head)
14: {
15: int len = strlen(in.head->u.str);
16: int pos;
17:
18: if (len > whichByte)
19: pos = (unsigned char)
20: in.head->u.str[whichByte];
21: else
22: pos = 0;
23: appendNode(&table[pos], removeHead(&in));
24: }
25: for (i = 1; i < UCHAR_MAX + 1; i++)
26: concatList(&table[0], &table[i]);
27: return table[0];
28: }
29 

30: /* Sort strings using radix sort */
31: void sortStrings(const char *array[])
32: {
33: int i;
34: int len;
35: int maxLen = 0;
36: list_t list;
37:
38: list.head = list.tail = NULL;
39: for (i = 0; array[i]; i++)
40: {
41: appendNode(&list,
42: newNode((void *) array[i]));
43: len = strlen(array[i]);
44: if (len > maxLen)
45: maxLen = len;
46: }
47: for (i = maxLen - 1; i >= 0; i--)
48: list = radixSort(list, i);
49: for (i = 0; array[i]; i++)
50: array[i] = removeHead(&list)->u.str;
51: }

Cross Reference:

III.1: What is the easiest sorting method to use?
III.3: How can I sort things that are too large to bring into memory?
III.7: How can I sort a linked list?