Finding the k th Smallest Value of an Array High level pseudocode solution: Your

Question

Finding the kth Smallest Value of an Array

High level pseudocode solution:

Your task is to implement and test the algorithm

Returns the kth smallest value in anArray[first..last] kSmallCk: integer anArray: ArrayType first integer, last integer) ValueType Choose a pivot value p from an Array[first. .last] Partition the values of anArray[first. .last] about p if (k pivot Index first 1) return k Small Ck, anArray, first, pivotIndex 1) else if (k pivot Index first 1) return p else return k Small (k (pivot Index first 10, anArray, pivot Index 1, last

Explanation / Answer

Algo:-

1)sort the given array using a sorting algorithm like Merge Sort, Heap Sort (it takes o(nlogn) time) etc .

2)return the element at index k-1 in the sorted array.

Time Complexity of this solution is O(nLogn)

---------------------------------------------------------------------

#include<iostream>
#include<algorithm>
using namespace std;

//This function take a unsorted array and size of array and a return kth smallest element

int kthSmallest(int array[], int n, int k)
{
// This function sort the array
sort(array, array+n);

// Return k'th element in the sorted array
return array[k-1];
}

int main()
{
int array[] = {12, 3, 5, 7, 19};
int n = sizeof(array)/sizeof(array[0]), k = 3;
int kthelement= kthSmallest(array, n, k);
cout << k<< "th smallest element is " << kthelement<<endl;
return 0;
}
/*
output:-
3th smallest element is 7
*/

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.