kSmall(k: integer, anArray: ArryType, first: integer, last: intger) :ValueType c
ID: 3860459 • Letter: K
Question
kSmall(k: integer, anArray: ArryType, first: integer, last: intger) :ValueType
choose a pivot value P from anArray[first..last] partition the value of anArray[first..last]about P
if (k < pivotIndex - first + 1) return kSmall (k, anArray, first, pivotIndex -1)
else
if (k == pivotIndex - first + 1)
retun P
else
return kSmall (k - (paivotIndex - first + 1) , anArray, pivotIndex + 1 ,last)
Finding the kth Smallest Value of an Array
High level pseudocode solution:
Your task is to implement and test the algorithm
Explanation / Answer
#include <iostream>
using namespace std;
const int SIZE = 5;
int kSmall(int k, const int anArray[], int first, int last);
void partition(int anArray[], int size, int pivotValue, int& pivotIndex);
int main()
{
return 0;
}
int kSmall(int k, int anArray[], int first, int last)
{
int pivotIndex = first;
int p = anArray[first];
partition(anArray, SIZE, int pivotValue, pivotIndex);
if(k < pivotIndex - first + 1)
{
return kSmall(k, anArray, first, pivotIndex - 1)
}
else if(k == pivotIndex - first + 1)
{
return p;
}
else
{
return kSmall(k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last);
}
}
void partition(int anArray[], int first, int last, int& pivotIndex)
{
int pivot = anArray[first];
int lastS1 = first;
int firstUnknown = first + 1;
for(; firstUnknown <= last; ++firstUnknown)
{
if(anArray[firstUnknown] < pivot)
{
++lastS1;
swap(anArray[firstUnknown], anArray[lastS1]);
}
}
swap(anArray[first], anArray[lastS1]);
pivotIndex = lastS1;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.