IMPORTANT : C++ PROGRAM Write a function that takes an array Arr of size N and r
ID: 3575656 • Letter: I
Question
IMPORTANT : C++ PROGRAM
Write a function that takes an array Arr of size N and returns another array which, first disregards the numbers greater than a certain threshold (also a passed parameter), and then stores the remaining elements of the array Arr first in an increasing order and then in a decreasing order
Example: If Arr = {5,4,1,12,0,2} and threshold = 10, the returned array should be = {0,1,2,4,5,5,4,2,1,0}
In the main method, the user is asked to enter the size of array Arr, the value of the threshold, as well as all the elements of array Arr.
Notes and hints:
Write an iterative merge sort method to do the sorting part.
You may need to define additional functions.
The size of the returned array is dynamic (depending on the number of eliminated elements). Be careful how you return such an array.
Explanation / Answer
C++ Program:
/*
* C++ Program to Implement Merge Sort
*/
#include <iostream>
using namespace std;
#include <conio.h>
void merge(int *,int, int , int );
// Performs merge sort on the intput array
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
// Merger function in Merge Sort
void merge(int *a, int low, int high, int mid)
{
int i, j, k, c[high+1];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}
// Removes the values above threshold value and then prepares a final array with valid elements
// first in the ascending order and then in the reverse order
int* processArray(int *a, int size, int threshold){
int countAboveThreshold = 0;
// Count values in the array above given threshold
for(int i=0; i<size;i++){
if(a[i] > threshold)
countAboveThreshold++;
}
// New size with elements above threshold removed
int newSize = size-countAboveThreshold;
// Prepare new arrray with double the new Size
int *final = new int[newSize*2];
int p=0;
for(int i=0; i<size;i++){
if(a[i] <= threshold){
final[p] = a[i];
p++;
}
}
// Sort first half of the final array using merge sort
mergesort(final, 0, newSize-1);
int finalLength = newSize*2;
// Copy over the second half in reverse orde
for (int i = 0; i < newSize; i++)
{
final[finalLength-1-i] = final[i];
}
cout<<" Final sorted array ";
// Print the final sorted array
for (int i = 0; i < finalLength; i++)
{
cout<<final[i]<<" ";
}
// Return pointer to the final array
return final;
}
int main()
{
int i, size, threshold;
cout<<"Enter the number of elements in the array ";
cin>>size;
int a[size];
cout<<"Enter the elements: ";
for (i = 0; i < size; i++)
{
cin>>a[i];
}
cout<<"Enter the threshold value ";
cin>>threshold;
int *result = processArray(a, size, threshold);
}
-------------------------------------------------------------------------------------------------------------------------
Sample Output:
Enter the number of elements in the array
8
Enter the elements:
8 7 6 5 4 3 2 1
Enter the threshold value 5
Final sorted array
1 2 3 4 5 5 4 3 2 1
--------------------------------
Process exited after 13.96 seconds with return value 0
Press any key to continue . . .