Implement the algorithm kSmall as a C++ recursive function. Use the first value of the array as the pivot. We are given an input file and a main.cpp file to edit (which i put down below)

We need to partition the array to put numbers smaller than pivot on the left side and numbers bigger than the pivot on the right side. Here is a description in our text:

Given main.cpp file:

////////////////////////////////

#include #include

int main(){

//Declerations (insert as needed) int kSmall_pos; //For User Input int kSmall_val=0; //Populate using your algorithm implementation int pivot; //Pivot position in array

//User Input DO NOT MODIFY std::cout>kSmall_pos;

//File Read code (insert) - This code should be able to parse the data in a text file similar to the provided one and store values in an array for processing.

//kmsall algorithm implementation or function call (insert) - implement using recursion as indicated

//Log file output (insert) - preferred in .txt format acoording to instructions posted on assignment page

//Output DO NOT MODIFY std::cout

//////////////////////////////////

Given Input.txt

//////////////////////////////////

33 34 12 29 6 49 24 19 87 8 95 25 35 77 9 45 83 43 75 70 94 30 73 76 78 7 10 22 88 91 41 71 96 55 80 97 16 3 31 64 18 46 61 21 5 23 89 11 98 82 53 79 86 39 54 72 15 52 4 56 57 99 63 40 67 28 69 90 92 2 68 47 60 36 38 44 93 37 42 20 48 51 59 62 32 58 74 1 66 13 17 84 81 50 14 26 65 27 85 

////////////////////////////////

FIGURE 2-15 A partition about a pivot 2 first last pivotIndex 2. IfS, contains k -1 values, the kth smallest value must be the pivot p. This is the base case; it occurs if k pivo tIndex - first +1 3. If S contains fewer than k-1 values, the kth smallest value in anArray[first..1ast] must be in S2. Because Si contains pivot Index- first values, the kth smallest value in anArray [first . . 1 ast] is the (k-pivotIndex- first + 1))" smallest value in S2. This case occurs if k> pivotIndex - first+1. A recursive definition can summarize this discussion. Let kSmall (k, anArray, first, last)=k" smallest value in anArray[first..!ast] After you select the pivot value p and partition anArray[first..last] into S, and S,, you have that kSmall(k, anArray, first, last) equals kSmall (k, anArray, first, pivotIndex-1) ifkpivotIndex-first+1 p ifk pivotIndex -first+1 kSmall (k- (pivotIndex-first + 1), anArray, pivotIndex + 1, last) if k > pivotIndex -first+1