Please use C 11 Define a kelement partial sort of a vector v

Please use C++ 11.

Define a k-element partial sort of a vector v, where 0 < k < v.size(), to be a permutation (i.e., rearrangement) of the elements of v in which: the smallest value is placed in v[0]; the second-smallest value is placed in v[1]; and so on until the k-th smallest value is placed in v[k-1]; and the remaining values are stored in the remaining elements of v without any ordering restrictions. For example, if v is a 9-element vector with the values 3 0 19 77 -4 11 22 13 2, then:

• -4 0 19 77 3 11 22 13 2 and -4 0 77 11 3 19 2 13 22 are both 2-element partial sorts of v, and

• -4 0 2 3 11 19 13 77 22 is one possible 5-element partial sort of v.

a.State the invariant condition on the array elements at the end of the ith loop in Selection Sort.

b.Modify Selection Sort to become an O(n· k) algorithm for solving the k-element partial sorting problem. Write your solution in the space below. [HINT: How many iterations do you need for this new problem?]

template void k_select(vector &v, int k) {

Solution

//Modified selection sort to become O(nk) algorithm for solving the k element partial sorting problem.

void k_select(vector &v,int k)

{

int len=v.size();

for(i=0; i<k; i++)
   {
       for(j=i+1; j<len; j++)
       {
           if(v[i]>v[j])
           {
               temp=v[i];
                v[i]=v[j];
                v[j]=temp;
           }

       }

//Following code in comment prints the invariant condition on the array at the end of ith loop
       /*   for(i=0; i<len; i++)
           {
               cout<<v[i]<<\" \";
           }
               cout<<\"\ \";
       */     
   }

}