Linked List Radix Sort

Introduction:

For your third project you will implement the Radix sort method for sorting integer sequences. As part of this implementation you will create functions for manipulating singly linked lists. The algorithms for implementing linked lists will be discussed in your classes. Therefore, this description does not list implementation details of the required functions.

Radix Sort:

For this sort, you choose a number of "buckets" B (i.e. the radix). This program will use B = 10 - the number of numerals used in a decimal representation of a value. N will be the exponent for a power of 10 corresponding to the most significant digit in any number in the sequence S₀ = {S₀, S₁, ..., S_m} to be sorted. For example, if the largest value in the list has four digits (e.g. 3871), then N = 3, since 10³ is a four digit number.

Radix sort distributes the elements in the buckets by digits, starting from the least significant to most significant. In the first pass the numbers are placed into buckets based on the value of the least significant digit. After that, a new sequence S₁is created by stitching the bucket lists in order from the 0th to 9th. Next, the elements of S₁, are distributed in the buckets by the value of second digit (the tens place) and so on, up to the max number of digits.

Create 10 buckets/lists
Generate random values and place them in an unsorted linked list
Print the unsorted list
Determine N
for n = 0 to N do
for all numbers in sequence Sn
put the number in the bucket corresponding to the n-place digit
Stitch the bucket lists together from 0th to 9th to create Sn+1

Print the sorted list

Note that when the algorithm completes, the only non-empty bucket is bucket 0.

To illustrate the algorithm we will sort the sequence S₀ = {32, 100, 11,554, 626, 122, 87,963, 265, 108,9}. We start by distributing elements of S₀ by the value of 0-place digit (the one's place):

bucket 0: 100
bucket 1: 11
bucket 2: 32, 122
bucket 3: 963
bucket 4: 554
bucket 5: 265
bucket 6: 626
bucket 7: 87
bucket 8: 108
bucket 9: 9

Stitch the bucket lists to create S₁ = {100, 11, 32, 122,963,554, 265, 626, 87, 108,9}. Distribute elements of S₁, by the value of 1-place digit (the ten's place):

bucket 0: 100, 108,9
bucket 1: 11
bucket 2: 122, 626
bucket 3:32
bucket 4:
bucket 5: 554
bucket 6: 963, 265
bucket 7:
bucket 8: 87
bucket 9:

Stitch the bucket lists to create S₂ = {100, 108, 9, 11, 122, 626, 32,554,963, 265, 87}. Distribute elements of S₂ by the value of 2-place digit (the hundred's place):

bucket 0: 9, 11, 32, 87
bucket 1: 100, 108, 122
bucket 2: 265
bucket 3:
bucket 4:
bucket 5: 554
bucket 6: 626
bucket 7:
bucket 8:
bucket 9: 963

Stitch the bucket lists to create S₃ = {9, 11, 32, 87, 100, 108, 122,265,554, 626, 963}. The list is sorted.

Detailed requirements for linked lists implementation:

You will need to write several functions.

0. To represent a node in a linked list you can use a structure

typedef struct Node
{
Some DataType data;
struct Node *next;
} ListNode;

where SomeDataType can be any C data type.

1. Write a function to make a new list. Your function should create a dummy head node to represent an empty list.

ListNode *newList(void); /* returns a head of a new empty list */

2. Write functions to insert elements into a list and to remove elements from a list (Note: These are suggested functions. You may have additional functions, or different function prototypes than those shown)

ListNode *removeNode(ListNode * prev); /* remove the node after prev from the list, and returns a pointer to the removed node */
ListNode *insertNode(ListNode *prev, SomeDataType data); /* inserts a new node with data field data after prev and returns a pointer to the new node */

3. Write functions to count the number of elements in a list without the head and to print the list

int length(ListNode *head); /* number of elements in the list */
void printList(ListNode *head); /* print the data fields for the entire list */

Note that printList will print the linked list implemented to support the second part of your project.

To make radix sort more efficient you will find it useful to implement a function ListNode insert at tail(ListNode *tail, SomeDataType data). The function should attach a new node to the tail and make that node the new tail of the list. You should also implement a delete List(ListNode *head) function which can be used to delete an entire list.

Detailed requirements for radix sort implementation:

You will need to write the functions for the linked lists implementation and the main RadixSort.c program that will generate N random integers in the range [low ... high). Your program should take 4 arguments: a seed for the random number generator, the number of values to sort, and low and high values to denote the range of values:

RadixSort RNG_Seed NumVals low Val high Val

Your program has to include error checking and debugging code. It must compile with no warnings using the following compile flags:

CFLAGS = -Wall -g -std=c89-D_XOPEN_SOURCE=600 -pedantic-errors

You have to free all memory before exiting the program-i.e. delete all linked lists. You will run valgrind as part of your submission typescript so use it during development and debugging to ensure there are no memory leaks or dangling pointers.