+1 (315) 557-6473 

Create a Program to Implement Radix Sort in C++ Assignment Solution.


Instructions

Objective
Write a program to implement radix sort in C++.

Requirements and Specifications

program to implement radix sort in C++

Source Code

#include

#include

#include

#define NUM_BUCKETS 10

#define TRUE 1

#define FALSE 0

/* Used for building linked-list */

typedef struct _ListNode

{

int data;

struct _ListNode *next;

} ListNode;

/* Function prototypes */

ListNode *newList(void);

ListNode *removeNode(ListNode *prev);

ListNode *insertNode(ListNode *prev, int data);

void deleteList(ListNode *current);

int length(ListNode *head);

void printList(ListNode *head);

/* Entry point of the program */

int main(int argc, char *argv[])

{

ListNode *headNodes[NUM_BUCKETS], *tailNodes[NUM_BUCKETS];

ListNode *listHead, *listTail, *current;

int i, flag, divisor, index, iteration;

int seed;

int numValues;

int minValue, maxValue, value;

/* Validate the arguments */

if (argc != 5)

{

printf("Usage: %s \n", argv[0]);

return 0;

}

if (sscanf(argv[1], "%d", &seed) != 1)

{

printf("The seed should be an integer\n");

return 0;

}

if (sscanf(argv[2], "%d", &numValues) != 1 || numValues <= 0)

{

printf("The number of values should be a positive integer\n");

return 0;

}

if (sscanf(argv[3], "%d", &minValue) != 1)

{

printf("The minimum value should be a positive value\n");

return 0;

}

if (sscanf(argv[4], "%d", &maxValue) != 1 || maxValue <= minValue)

{

printf("The maximum value should be a positive value higher than the minimum value\n");

return 0;

}

/* Seed the random number generator */

srand(seed);

/* Reset the buckets with empty list */

listHead = NULL;

listTail = NULL;

for (i = 0; i < NUM_BUCKETS; i++)

{

headNodes[i] = NULL;

tailNodes[i] = NULL;

}

/* Generate random values and put them in an unsorted list */

for (i = 0; i < numValues; i++)

{

value = (rand() % (maxValue - minValue)) + minValue;

if (listHead == NULL)

{

listHead = newList();

listHead->data = value;

listTail = listHead;

}

else

{

listTail = insertNode(listTail, value);

}

}

/* Print out the unsorted list */

iteration = 0;

printf("Iteration %d: ", iteration);

printList(listHead);

/* Now do the radix sort */

flag = TRUE;

divisor = 1;

while (flag)

/* Flag identifies if we're done iterating */

flag = FALSE;

/* Re-distrbute the list values to the buckets */

current = listHead;

while (current != NULL)

{

index = (current->data / divisor) % 10;

if (index > 0)

flag = TRUE;

if (headNodes[index] == NULL)

{

headNodes[index] = newList();

headNodes[index]->data = current->data;

tailNodes[index] = headNodes[index];

}

else

{

tailNodes[index] = insertNode(tailNodes[index], current->data);

}

current = current->next;

}

/* Merge back the elements from buckets to the main list in-order */

deleteList(listHead);

listHead = NULL;

listTail = NULL;

for (i = 0; i < NUM_BUCKETS; i++)

{

current = headNodes[i];

while (current != NULL)

{

if (listHead == NULL)

{

listHead = newList();

listHead->data = current->data;

listTail = listHead;

}

else

{

listTail = insertNode(listTail, current->data);

}

current = current->next;

}

deleteList(headNodes[i]);

headNodes[i] = NULL;

tailNodes[i] = NULL;

}

/* Check out our new list */

iteration++;

printf("Iteration %d: ", iteration);

printList(listHead);

/* Move to the next digit .. (e.g. ones, tens, hundreds... ) */

divisor *= 10;

}

/* Clean up */

deleteList(listHead);

return 0;

}

/* Create a new empty list */

ListNode *newList(void)

{

ListNode *node;

node = malloc(sizeof(ListNode));

node->data = 0;

node->next = NULL;

return node;

}

/* Remove the node after the previous node */

ListNode *removeNode(ListNode *prev)

{

ListNode *removedNode;

if (prev == NULL || prev->next == NULL)

return NULL;

removedNode = prev->next;

prev->next = removedNode->next;

return removedNode;

}

/* Insert a new value after the previous node*/

ListNode *insertNode(ListNode *prev, int data)

{

ListNode *insertedNode;

if (prev == NULL)

return NULL;

insertedNode = newList();

insertedNode->data = data;

insertedNode->next = prev->next;

prev->next = insertedNode;

return insertedNode;

}

/* Deallocate the nodes */

void deleteList(ListNode *current)

{

ListNode *next;

if (current == NULL)

return;

while (current != NULL)

{

next = current->next;

free(current);

current = next;

}

}

/* Return the number of elements */

int length(ListNode *head)

{

int count;

ListNode *current;

ount = 0;

current = head;

while (current != NULL)

{

count++;

current = current->next;

}

return count;

}

/* Print the entire list contents */

void printList(ListNode *head)

{

ListNode *current;

current = head;

while (current != NULL)

{

printf("%d ", current->data);

current = current->next;

}

printf("\n");

}