Subject Computer Science C-Family Programming

Question

Part A of OPTION 2: Radix-Sort
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;...

This is only a preview of the solution. Please use the purchase button to see the entire solution

$40.00

or free if you
register a new account!

Related Homework Solutions

Get help from a qualified tutor
Live Chats