Write a C++ version of the following Java program that performs all the same fun
ID: 3680671 • Letter: W
Question
Write a C++ version of the following Java program that performs all the same functions:
import java.util.Arrays;
import java.util.Scanner;
public class RadixSort {
// do not instantiate
private RadixSort() { }
// The main function to that sorts String[] of size n using
// Radix Sort
public static void sort(String[] a, int W) {
int N = a.length;
int R = 256; // extend ASCII alphabet size
String[] aux = new String[N];
for (int d = W-1; d >= 0; d--) {
// sort by key-indexed counting on dth character
// compute frequency counts
int[] count = new int[R+1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
// compute cumulates
for (int r = 0; r < R; r++)
count[r+1] += count[r];
// move data
for (int i = 0; i < N; i++)
aux[count[a[i].charAt(d)]++] = a[i];
// copy back
for (int i = 0; i < N; i++)
a[i] = aux[i];
}
}
// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void sort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String name;
System.out.print("Enter you name and course section : ");
name = sc.nextLine();
int[] List1 = new int[]{123, 3, 151, 234, 701, 181, 401, 924, 155, 233, 456, 735, 412, 6};
int[] List2 = new int[]{100, 191, 101, 192, 222, 245, 222, 235};
String[] List3 = new String[]{"MEL", "TOD", "TOM", "JAC", "CUB", "KOB", "KID", "PLY","MIC", "ABC"};
sort(List1,List1.length);
sort(List2,List2.length);
sort(List3,3); // 3 is length of each string
System.out.println("Your Name: "+name);
System.out.print("Sorted list1: ");
for (int i = 0; i < List1.length; i++)
System.out.print(List1[i]+" ");
System.out.println();
System.out.print("Sorted list2: ");
for (int i = 0; i < List2.length; i++)
System.out.print(List2[i]+" ");
System.out.println();
System.out.print("Sorted list2: ");
for (int i = 0; i < List3.length; i++)
System.out.print(List3[i]+" ");
System.out.println();
}
}
Explanation / Answer
// .h file for above program
#pragma once
#include <string>
#include <vector>
#include <iostream>
class RadixSort
{
// do not instantiate
private:
RadixSort();
// The main function to that sorts String[] of size n using
// Radix Sort
public:
static void sort(std::vector<std::wstring> &a, int W);
// A utility function to get maximum value in arr[]
static int getMax(std::vector<int> &arr, int n);
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(std::vector<int> &arr, int n, int exp);
// The main function to that sorts arr[] of size n using
// Radix Sort
static void sort(std::vector<int> &arr, int n);
static void main(std::vector<std::wstring> &args);
};
// .cpp file for above program
#include "RadixSort.h"
RadixSort::RadixSort()
{
}
void RadixSort::sort(std::vector<std::wstring> &a, int W)
{
int N = a.size();
int R = 256; // extend ASCII alphabet size
std::vector<std::wstring> aux(N);
for (int d = W - 1; d >= 0; d--)
{
// sort by key-indexed counting on dth character
// compute frequency counts
std::vector<int> count(R + 1);
for (int i = 0; i < N; i++)
{
count[a[i][d] + 1]++;
}
// compute cumulates
for (int r = 0; r < R; r++)
{
count[r + 1] += count[r];
}
// move data
for (int i = 0; i < N; i++)
{
aux[count[a[i][d]]++] = a[i];
}
// copy back
for (int i = 0; i < N; i++)
{
a[i] = aux[i];
}
}
}
int RadixSort::getMax(std::vector<int> &arr, int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > mx)
{
mx = arr[i];
}
}
return mx;
}
void RadixSort::countSort(std::vector<int> &arr, int n, int exp)
{
std::vector<int> output(n); // output array
int i;
std::vector<int> count(10);
Arrays::fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
{
count[(arr[i] / exp) % 10]++;
}
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
{
arr[i] = output[i];
}
}
void RadixSort::sort(std::vector<int> &arr, int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
{
countSort(arr, n, exp);
}
}
void RadixSort::main(std::vector<std::wstring> &args)
{
Scanner *sc = new Scanner(System::in);
std::wstring name;
std::wcout << std::wstring(L"Enter you name and course section : ");
name = sc->nextLine();
std::vector<int> List1 = {123, 3, 151, 234, 701, 181, 401, 924, 155, 233, 456, 735, 412, 6};
std::vector<int> List2 = {100, 191, 101, 192, 222, 245, 222, 235};
std::vector<std::wstring> List3 = {L"MEL", L"TOD", L"TOM", L"JAC", L"CUB", L"KOB", L"KID", L"PLY",L"MIC", L"ABC"};
sort(List1,List1.size());
sort(List2,List2.size());
sort(List3,3); // 3 is length of each string
std::wcout << std::wstring(L"Your Name: ") << name << std::endl;
std::wcout << std::wstring(L"Sorted list1: ");
for (int i = 0; i < List1.size(); i++)
{
std::wcout << List1[i] << std::wstring(L" ");
}
std::wcout << std::endl;
std::wcout << std::wstring(L"Sorted list2: ");
for (int i = 0; i < List2.size(); i++)
{
std::wcout << List2[i] << std::wstring(L" ");
}
std::wcout << std::endl;
std::wcout << std::wstring(L"Sorted list2: ");
for (int i = 0; i < List3.size(); i++)
{
std::wcout << List3[i] << std::wstring(L" ");
}
std::wcout << std::endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.