## Question

The purpose of Part A is to implement a radix-sort based algorithm for sorting 32-bit unsigned integers. A 32-bit unsigned integer can be viewed as an 1-digit radix-232 − 1 integer, or a 2-digit radix-65536 integer, or a 4-digit radix-256 integer. For JAVA implementations one may assume that the input is a 31-bit non-negative integer.

void rdx_sort (unsigned int *keys, int n,

rdx_sort (int[] keys, int n,

keys

n

mradix

unsigned int mradix);

unsigned int mradix);

// C or C++

// Java

: is a pointer to the input array of unsigned int data type.

: is the dimension (number of elements) of the array.

: is the radix that will be used; each integer is viewed ad d-digit radix-mradix integer.

1. If mradix = 256, your algorithm should behave like a RadixSort algorithm and view the integers as 4-digit radix-256 numbers,

2. otherwise, if mradix = 65536, your algorithm should behave like a RadixSort algorithm and view the integers as 2-digit radix-65536 numbers,

3. otherwise, if n ≥ mradix , your algorithm should behave like CountSort,

4. otherwise, if n < mradix , then your algorithm should automatically decide the radix between radix-256 and radix-65536 and revert to a radix-sort based algorithm (i.e. choose between (1) and (2)).

Remark. Note the order of the if-otherwise statement above. If n = 10000 and mradix = 256, case 1 applies, even if case 3 is also applicable.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <stdio.h>#include <stdlib.h>

#include <string>

#include <math.h>

using namespace std;

void rdx_sort (unsigned int *keys, int n, unsigned int mradix);

int main()

{

int n = 100;

unsigned int mradix = 256;

unsigned int *keys;

keys = new unsigned int[n];

printf("Original List:\n");

for(int i = 0; i < n; i++)

{

keys[i] = rand();

keys[i] <<= 16;

keys[i] += rand();

keys[i] <<= 1;

keys[i] += rand()%2;...

By purchasing this solution you'll be able to access the following files:

Solution.cpp.