I need an improved search algorithm that can be implemented into the given code that isnt as redundant as the brute force algorithm provided.

#include  #include  #include  #include  #include  int InsertionSort(int* array, int arraySize){ int numComparisonsSorting = 0; for (int i = 1; i = 0){ numComparisonsSorting++; if (array[j] > value) array[j+1] = array[j]; else break; j--; } array[j+1] = value; } return numComparisonsSorting; } 

int main(){ using namespace std; int numElements; cout > numElements; int maxValue; cout > maxValue; srand( static_cast(time(nullptr))); int* array = new int[numElements]; int *sortedArray = new int[numElements]; // will be sorted after filled. // filling up the arrays for (int index = 0; index  
number of elements (n) = 100
 
maxVal (m) = 40
  You are given the C++ code that does a brute force search using a nested ijk loop on an arbitrary array (of size numElements, corresponding to variable ' n ' in this assignment description) of integers ranging from 1...maxVal (where max Val corresponds to variable ' m ' in this assignment description). The range of the targetSum values is from maxVal to 3 maxVal. The code keeps track of the number of comparisons (referred to as numComparisonsBruteForce in the startup code) involved to identify all the 3 -element tuples that add up to each of the 'targetSum' values (referred to as 't' in the assignment description) and prints them. Your task in this assignment is to come up with an improved search algorithm and its implementation that does better (with respect to the number of comparisons as well as the number of additions; for more explanation on the number of additions, see the separate paragraph below) than the brute force search whose implementation is given to you as part of the startup code. The improved search algorithm is to be implemented in the space provided in the startup code. The algorithm should identify all the 3-element tuples (with as low redundancy as possible) that add up to a particular targetSum value and keep track of the number of comparisons (referred to as 'numComparisonsImprovedSearch' in the startup code) and the number of additions (referred to as 'numAdditionsImprovedSearch' in the startup code) involved to identify all such 3-element tuples. You are also given the code for the Insertion Sort algorithm that can be used to sort the arbitrary array and run your "improved search algorithm" for a particular targetSum value on the sorted array. The code for the Insertion sort algorithm returns the number of comparisons involved in the sorting process so that this overhead can be added to the numComparisonsImprovedSearch variable that keeps track of the total number of comparisons encountered to identify all the 3-element tuples that add up to a targetSum value. 2) A PDF file that contains the following: 2.1: A pseudo code for your improved search algorithm 2.2: A description of the logic you have incorporated in the improved search algorithm to reduce the number of comparisons and the number of additions 2.3: The output (included with a reduced font as shown below in the sample output) printed by your code for the ' n ' and 'm' values (see below) assigned to you. 2.4: A plot of the targetSum value in the X-axis vs. the number of comparisons encountered by the brute force search and the improved search algorithm in the Y-axis. 2.5: A plot of the targetSum value in the X-axis vs. the number of additions encountered by the brute force search and the improved search algorithm in the Y-axis. 2.6: An interpretation of your results as observed in 2.3, 2.4 and 2.5. Make sure to discuss: 2.6.1: the distribution of the values (constant or monotonic increase or monotonic decrease) in the number of comparisons and number of additions encountered with the brute force search and the improved search algorithms. 2.6.2: Does the number of comparisons with the improved search always remain lower than the brute force search or does it get larger? If the latter case is observed, why and when does it happen