Program 1- Radix Sort via Linked Lists

Due: February 11, 2002, 11AM by email


This programming assignment gives you practice with linked lists and an interesting algorithm - Radix Sort. Write a program that uses Radix Sort to sort N integers in a specified range, 0 to M. (N and M are input.)

Your driver program should test the sort by generating random numbers in this range. Your program should output the array of numbers before sorting, and after it is sorted.

The sort itself should use an array of Linked Lists, following the algorithm discussed in class. You will find it useful to have methods in your Linked List class that append two lists (concatenate the second list to the end of the first),  and tailInsert, to insert an element at the tail of a list. You can build your Linked List class following the text's, or write your own (without iterators).