Programming Praxis

It is well known that any comparison-based sort, as we have been studying, has a lower time bound of O(n log n). But if all the keys are positive integers less than or equal to n, it is possible to sort in O(n) linear time by taking advantage of the structure of the keys themselves.

Count sort determines, for each input element x, the number of elements less than x, then places x directly in its position in the output; if there are k elements less than x, then x belongs in the k^th + 1 position (being careful to properly consider the case of equal elements). Count sort requires two temporary arrays, one to hold the counts of the various elements, which act as indexes into the array, and one to build up the output.

Radix sort extends count sort by making multiple passes based on the positional digits of the integers being sorted: first do a count sort on the digits in the ones column of the integers, then a count sort on the digits in the tens column, then the hundreds column, the thousands column, and so on until the input is sorted, taking advantage of the fact that count sort is stable. Radix sort works on other kinds of keys besides integers; for instance, dates can be sorted by doing count sort on day, month and year in succession.

Your task is to write functions that sort arrays using count sort and radix sort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2