PROG $20799-$ Assignment $4$ and Project Part B

Due date: Please check the SLATE drop box. Late assignments will be penalized according to the class plan outline.

You can use class example solutions $($as a starting point$)$ for this assignment.

This assignment will be graded out of $10$ and worth $5\%$ of your total marks for this course.

Submission requirements:

Assignment $4$

Upload the radixSort.c to the SLATE drop box only. Otherwise, $10\%$ will be deducted.

Do not zip the files; otherwise, $10\%$ will be deducted from your final mark of this assignment.

Do not change any function names; otherwise, $20\%$ will be deducted from your final mark of this assignment.

Project

Upload all the related program files and your report to the SLATE drop box.

For this assignment, you are required to implement a radix sort following the given algorithm below. You must use a queue ADT for this program and not include any other algorithms, such as counting sort. If your program contains other algorithm$($s$),$ your assignment will be automatically graded as zero.

Create five functions:

generateArray$()-$ This function creates an array that contains one hundred random numbers.

findBiggest $O-$ This function finds the biggest number in the array.

getNumberOfRuns $()-$ This function calculates the total number of runs required.

radixSort$()-$ This function performs ascending sorting.

display $(-$ This function displays the sorted array on a screen.

You are free to design the prototypes for these five functions.

Radix sort algorithm

Array: $459,254,472,534,649,239,432,654,477$

The total number of runs is determined by the number of digits in the biggest number in the array. For this example, since the biggest number is $654,$ which has three digits, the total number of runs is three.

The first run: place the numbers in the bin queues according to last digit.

The second run: place the numbers in the bin queues according to second last digit.

The third run: place the numbers in the bin queues according to third last digit.

Basically, radix sort works by iterating each digit of the numbers being sorted, from right to left, and sorting them based on that digit. It starts with the least significant digit and works its way up to the most significant digit.

Use enqueue and dequeue appropriately to place the numbers in the bin queues.

The entire process is shown below.

queueADT binQueue$[10]$

$\backslash$table$[[$Digit$,$Bin queue $(11^{st}$ run$),2^{nd}$ run,$3^{rd}$ run$],[0,,,],[1,,,]]$

The emure process is shown below.

queueADT binQueue$[10]$

$\backslash$table$[[$Digit$,$Bin queue $(11^{st}$ run