Mastering Algorithms With C - Kyle Loudon [140]
if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {
free(counts);
return -1;
}
/*****************************************************************************
* *
* Initialize the counts. *
* *
*****************************************************************************/
for (i = 0; i < k; i++)
counts[i] = 0;
/*****************************************************************************
* *
* Count the occurrences of each element. *
* *
*****************************************************************************/
for (j = 0; j < size; j++)
counts[data[j]] = counts[data[j]] + 1;
/*****************************************************************************
* *
* Adjust each count to reflect the counts before it. *
* *
*****************************************************************************/
for (i = 1; i < k; i++)
counts[i] = counts[i] + counts[i - 1];
/*****************************************************************************
* *
* Use the counts to position each element where it belongs. *
* *
*****************************************************************************/
for (j = size - 1; j >= 0; j--) {
temp[counts[data[j]] - 1] = data[j];
counts[data[j]] = counts[data[j]] - 1;
}
/*****************************************************************************
* *
* Prepare to pass back the sorted data. *
* *
*****************************************************************************/
memcpy(data, temp, size * sizeof(int));
/*****************************************************************************
* *
* Free the storage allocated for sorting. *
* *
*****************************************************************************/
free(counts);
free(temp);
return 0;
}
Description of Radix Sort
Radix sort is another efficient, linear-time sorting algorithm. It works by sorting data in pieces called digits, one digit at a time, from the digit in the least significant position to the most significant. Using radix sort to sort the set of radix-10 numbers {15, 12, 49, 16, 36, 40}, for example, produces {40, 12, 15, 16, 36, 49} after sorting on the least significant digit, and {12, 15, 16, 36, 40, 49} after sorting on the most significant digit.
It is very important that radix sort use a stable sort for sorting on the digit values in each position. This is because once an element has been assigned a place according to the digit value in a less significant position, its place must not change unless sorting on one of the more significant digits requires it. For example, in the set given earlier, when 12 and 15 were sorted on the digits in the most significant position, since both integers contained a "1," a nonstable sort may not have left them in the order they were placed when sorted by their least significant digit. A stable sort ensures that these two are not reordered. Radix sort uses counting sort because, aside from being stable, it runs in linear time, and for any radix, we know the largest integer any digit may be.
Radix sort is not limited to sorting data keyed by integers, as long as we can divide the elements into integer pieces. For example, we might sort a set of strings as radix-28 values. Or we might sort a set of 64-bit integers as four-digit, radix-216 values. Exactly what value we choose as a radix depends on the data itself and minimizing pn + pk considering space constraints, where p is the number of digit positions in each element, n is the number of elements, and k is the radix (the number of possible digit values in any position). Generally, we try to keep k close to and no more than n.
Interface for Radix Sort
Name
rxsort
Synopsis
int rxsort(int *data, int size, int p, int k);
Return Value
0 if sorting is successful, or -1 otherwise.
Description
Uses radix sort to sort the array of integers in data. The number of integers in data is specified by size. The argument p specifies the number of digit positions in each integer. The argument k specifies the radix. When rxsort returns,