Write a C++ version of the following Java program: import java.util.Arrays; impo

Question

Write a C++ version of the following Java program:

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

#include<iostream>

using namespace std;

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;

}

void countSort(int arr[], int n, int exp)

{

int output[n];

int i, count[10] = {0};

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

count[(arr[i]/exp)%10]++;

for(i = 1; i < n; i++)

count[i] +=count[i-1];

for(i = n-1; i >= 0; i--)

{

output[count[(arr[i]/exp)%10]-1] = arr[i];

count[(arr[i]/exp)%10]--;

}

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

arr[i] = output[i];

}

void radixsort(int arr[], int n)

{

int m = getMax(arr, n);

for(int exp = 1; m/exp >0; exp *= 10)

countSort(arr,n,exp);

}

void print(int arr[], int n)

{

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

cout << arr[i] <<" ";

}

int main()

{

int arr[] = {123, 3, 151, 234, 701, 181, 401, 924, 155, 233, 456, 735, 412, 6};

int n = sizeof(arr)/sizeof(arr[0]);

radixsort(arr, n);

print(arr, n);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.