Program Design II (PK2)

SML Assignment 3 of Spring 2006

Sorting in Linear Time: Radix Sort

Radix sort was originally used for mechanically sorting punch cards. The principle is to classify the given numbers first according to the least significant digit, then according to the second-least significant digit, and so on. For this to work, one needs to use a stable classification method: the order between two equal numbers must be preserved.

Radix sort is described in the Dictionary of Algorithms and Data Structures and in the Introduction to Algorithms textbook (errata), on pages 170 to 173 (you need not read up anything about counting sort, nor use a sorting algorithm to classify the numbers into the bins). You can choose any number k of bins (or buckets), corresponding to the base in which your algorithm views the given numbers, but you must indicate that base in your specification.

The additional knowledge of the maximal number d of digits of the n numbers in the list allows the design of such linear-time Θ(n) sorting algorithms (when d is a constant and k = O(n)). This beats, in theory, the O(n lg n) running time of comparison-based sorting algorithms that are not given any such knowledge.

The objective of this assignment is to assess the subtleties in efficiently implementing radix sort for lists and properly examining its actual efficiency.

  1. Implement radix sort for sorting in non-decreasing order (that is, any element is less than or equal to its successor, if any) a list L of natural numbers with maximum d digits in the chosen base k : radixSort L d : int list -> int -> int list, such that the running time for n elements is Θ(n).

    Example: radixSort [9821, 5674, 7890, 1234, 638] 4 = [638, 1234, 5674, 7890, 9821], assuming the algorithm has k = 10 bins, because all the n = 5 given numbers have maximum d = 4 digits in base k = 10. Use d = 14 if viewing those numbers in base k = 2 and thus using only k = 2 bins.

  2. Compare radix sort against merge-sort or quick-sort via experiments on the same random lists of 0 to 100,000 elements, by increments of 5,000 elements. Plot the running times in one diagram and give them in tabular form as well. Indicate how you generated the random lists of each length.

    To generate a random list, use   Random.rangelist (minimalElement, maximalElement) (numberOfElements, Random.newgen()). The interval between the smallest and largest possible values of a random list should be at least 100 times larger than the number of elements of that list, otherwise there will be too many duplicates in the generated lists. Many duplicates would mean that one examines an extreme case rather than a general, random case.

    To measure a running time, use the function timeIt in the file ranTime.sml, which takes a function f and an argument a and returns the running time for f applied to a.

    To plot the data of a file called   file.data, use the command   plot "file.data" with lines in   gnuplot. If you have several files, then write   plot "file1.data" with lines, "file2.data" with lines instead. If you want to produce a Postscript file, write   set terminal postscript and   set output "file.ps" before running the plot command again. A Unix command for converting Postscript to PDF is   ps2pdf.

  3. Are the results as expected? Why / Why not?

Submission

Your solution, prepared in compliance with the ethics rules of the course, must be submitted by the published deadline via the course manager system, and shall contain: