In: Computer Science
Please make my Code working and pass the test but do NOT change anything in main function, thank you.
#include <iostream>
using namespace std;
void sort(int *A, int n){
for(int passes = 0;passes < 2;passes++)
{
// shift can have only two values either 0 or 16, used for shifting purpose
int shift = passes * 16;
int N = 1<<(16 + 1);
// Temporary array for storing frequency of upper or lower 16 bits
int temp[N];
// initialze all value to zero at first
for(int i = 0;i < N;i++)
temp[i] = 0;
// storing the frequecy of either lower or upper half the every number
for(int i = 0;i < n;i++){
temp[(A[i] >> shift)&0xFFFF]++;
}
// making cummulative sum of the frequecies
for(int i = 1;i < N;i++)
temp[i] += temp[i-1];
// A temporary output array for storing ns
int output[n];
// storing the number in their requied position
for(int i = n - 1;i >= 0;i--)
{
output[ temp[(A[i] >> shift)&(0xFFFF)] - 1] = A[i];
temp[ (A[i] >> shift)&(0xFFFF) ]--;
}
// copy the values of temporary output array to original array
for(int i = 0;i < n;i++){
A[i] = output[i];
}
}
}
void sort( int *A, int n);
int main()
{
int i, offset, j;
int B[10000000];
time_t t;
srand( (unsigned) time( &t ));
offset = rand()%10000000;
for( i = 0; i< 10000000; i++ )
{
B[i] = ((91*i)%10000000) + offset;
}
printf("Prepared array of 10 million integers; calling sort\n");
sort( B, 10000000);
printf("finished sort, now check result\n");
for( i=0, j=0; i < 10000000; i++ )
if( B[i] != i+ offset ) j++;
if( j == 0 )
printf("Passed Test\n");
else
printf("Failed Test. %d numbers wrong.\n", j );
}
Solution- This code works successfully in Gcc 6.3, C++14 environment. Maybe, there is issue in the compiler itself.
Screenshot of code and IO -
In the following screenshot it is clear that the code gives the output that shows test cases passed.
Code
#include <iostream>
using namespace std;
void sort(int *A, int n){
for(int passes = 0;passes < 2;passes++)
{
// shift can have only two values either 0 or 16, used for shifting purpose
int shift = passes * 16;
int N = 1<<(16 + 1);
// Temporary array for storing frequency of upper or lower 16 bits
int temp[N];
// initialze all value to zero at first
for(int i = 0;i < N;i++)
temp[i] = 0;
// storing the frequecy of either lower or upper half the every number
for(int i = 0;i < n;i++){
temp[(A[i] >> shift)&0xFFFF]++;
}
// making cummulative sum of the frequecies
for(int i = 1;i < N;i++)
temp[i] += temp[i-1];
// A temporary output array for storing ns
int output[n];
// storing the number in their requied position
for(int i = n - 1;i >= 0;i--)
{
output[ temp[(A[i] >> shift)&(0xFFFF)] - 1] = A[i];
temp[ (A[i] >> shift)&(0xFFFF) ]--;
}
// copy the values of temporary output array to original array
for(int i = 0;i < n;i++){
A[i] = output[i];
}
}
}
void sort( int *A, int n);
int main()
{
int i, offset, j;
int B[10000000];
time_t t;
srand( (unsigned) time( &t ));
offset = rand()%10000000;
for( i = 0; i< 10000000; i++ )
{
B[i] = ((91*i)%10000000) + offset;
}
printf("Prepared array of 10 million integers; calling sort\n");
sort( B, 10000000);
printf("finished sort, now check result\n");
for( i=0, j=0; i < 10000000; i++ )
if( B[i] != i+ offset ) j++;
if( j == 0 )
printf("Passed Test\n");
else
printf("Failed Test. %d numbers wrong.\n", j );
}