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

Instructions

Objective

Write a C++ assignment that involves implementing radix sort. The goal of this program is to sort an array of integers using the radix sort algorithm, which is an efficient sorting technique based on the digits' positions in the numbers. The assignment should prompt the user to input the size of the array and its elements. Then, the program will perform radix sort on the input array and display the sorted result. The implementation should take into account both positive and negative integers.

Requirements and Specifications

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"); }