Thank you for your helpful answerAnd youd better pay attenti

9. (10 pts) Consider a problem of finding the k-th smallest element from vector A. Complete the following function. Hint Think of a divide-and-conquer type algorithm similar to quick sort. You may simply choose A[0] as the pivot. float kthsmailest (const vectorsfloat:t A, int k)

Solution

#include<bits/stdc++.h>

using namespace std;
int n;
int partition(vector<float>& arr, int l, int r);

// This function returns k\'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT

float kthSmallest1(vector<float>& arr, int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around last element and get
// position of pivot element in sorted array
int pos = partition(arr, l, r);

// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest1(arr, l, pos-1, k);

// Else recur for right subarray
return kthSmallest1(arr, pos+1, r, k-pos+l-1);
}

// If k is more than number of elements in array
return INT_MAX;
}

/*void swap(float *a, float *b)
{
float temp = *a;
*a = *b;
*b = temp;
}*/

float kthSmallest(vector<float>& A,int k)
{
return kthSmallest1(A, 0, n-1, k);
}

// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it
// and greater elements to right
int partition(vector<float>& arr, int l, int r)
{
float x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(arr[i], arr[j]);

i++;
}
}
swap(arr[i], arr[r]);
  
return i;
}

// Driver program to test above methods
int main()
{
float arr[] = {100,200,11,9,8,21};

cout<<\"Enter n for number of elements:\ \";

cin>>n;
cout<<\"Enter array elements\ \";

for(int i=0;i<n;i++)
cin>>arr[i];

cout<<\"Enter K \ \";
int k;
cin>>k;
vector<float> vec(arr, arr + n);
cout << \"K\'th smallest element is \" << kthSmallest(vec, k);
return 0;
}

============================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ kthsmall.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Enter n for number of elements:
5
Enter array elements
1
2
3
4
5
Enter K
4
K\'th smallest element is 4