Please write a C++ program: Note: Input requires user to cin. Input structure Yo
ID: 3828559 • Letter: P
Question
Please write a C++ program:
Note: Input requires user to cin.
Input structure You are going to apply RadixSort to sort vectors. The input starts with an integer number which indicates the number of vectors to be sorted. Then vectors follow, one vector per line. Each vector consists of 10 numbers where each number has a value in t0, 1, 2, 3 Entries of a vector are separated by a space.
Input structure You are going to apply Radix Sort to sort vectors. The input starts with an integer number which indicates the number of vectors to be sorted. Then vectors follow, one vector per line. Each vector consists of 10 numbers where each number has a value in {0, 1, 2, 3}. Entries of a vector are separated by a space. Output structure Output the sorted sequence of vectors, one per line. Vector i must appear before vector j in your output if and only if for some d element {1, 2, .... 10}, vector i is smaller than or equal to vector j on the dth entry, and the two vectors are equal for any of the first d - 1 entries. 3333322222 2322222222 1300210000 1300220000 2321222222 1;3;0;0;2;1;0;0;0;0; 1;3;0;0;2;2;0;0;0;0; 2;3;2;1;2;2;2;2;2;2; 2;3;2;2;2;2;2;2;2;2; 3;3;3;3;3;2;2;2;2;2; More precisely, the above output example has 6 lines since a "coutExplanation / Answer
// C++ implementation of Radix Sort
#include<iostream>
#include<vector>
using namespace std;
//CountSort function for the pos position
void countSort(vector<int> arr[], int n, int pos)
{
vector<int> * output; // output array
int i, count[4] = {0};
output = new vector<int>[n];
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ arr[i][pos]%4 ]++;
for (i = 1; i < 4; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ arr[i][pos]%4 ] - 1] = arr[i];
count[ arr[i][pos]%4 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current position
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function that sorts arr[] of size n using
// Radix Sort
void radixsort(vector<int> arr[], int n)
{
int vectorSize = 10;
// Do counting sort for every position.
for (int pos = vectorSize -1; pos >= 0 ; pos--)
countSort(arr, n, pos);
}
// A utility function to print an array
void print(vector<int> arr[], int n)
{
for (int i = 0; i < n; i++)
{
// use iterator to access the values
vector<int>::iterator v = arr[i].begin();
while( v != arr[i].end())
{
cout << *v << ";";
v++;
}
cout << endl;
}
}
// Main function to test the program
int main()
{
int n;
cin >> n;
vector<int> *arr;
arr = new vector<int>[n];
for(int i =0;i<n;i++)
{
for(int j =0;j<10;j++)
{
int num;
cin>>num;
arr[i].push_back(num);
}
}
radixsort(arr, n);
print(arr, n);
return 0;
}
Sample input:
5
3 3 3 3 3 2 2 2 2 2
2 3 2 2 2 2 2 2 2 2
1 3 0 0 2 1 0 0 0 0
1 3 0 0 2 2 0 0 0 0
2 3 2 1 2 2 2 2 2 2
Sample output:
1;3;0;0;2;1;0;0;0;0;
1;3;0;0;2;2;0;0;0;0;
2;3;2;1;2;2;2;2;2;2;
2;3;2;2;2;2;2;2;2;2;
3;3;3;3;3;2;2;2;2;2;