Find the Kth smallest value in a list
There are numerous methods for finding the Kth Smallest item in a list. Here are a few.
1. Sort the list and look in slot K-1. This takes order (O(n*log(n))) time.
2. Load the list into a min heap (O(n)) and extract the first K (O(k*log(n)))
This takes a total of O(n) + O(k*log(n)) which depends upon k. If K is O(n) then the total order of complexity is O(n*log(n)). If k is a "small" constant then the total order of complexity is O(n).
3. Use a min priority queue of size K. One pass through data list keeping the K
smallest so far in pq, discarding the rest. The order of complexity depends upon K. If K is O(n) then the total order of complexity could be as much as O(n*log(n)). If k is a "small" constant then the total order of complexity is O(n).
4. Find the 1st smallest, then second smallest, ... Kth smallest. The order of complexity is
O(n + n-1 + ... + n-k) which again depends upon K; similar to the above.
Perhaps the best method is the following.
5. Let A be an array of N integers.
The core of the method is a call to Partition(A, N) to partition the array into 2 sub arrays. The sub arrays are divided into a left part and a right part and are separated by a "split value" which was, originally A[0].
Function KSmall(A, N, k)
//return the kth smallest value
goal = k; adjust = 0;
si = Partition(A, N)
while(si != goal)
if K < si //then the kth smallest value is in the left half of the array
then N = si
si = Partition(A, si)
else adjust = adjust + si + 1
N = N - adjust
goal = goal - adjust
si = Partition(A+adjust, N)
end while
return A[si+adjust]
end function kSmall
int Partition(int A[], N)
//splitLoc is the index of A such that A[i] <= A[j] whenever i <=splitLoc and j > splitLoc.
//Partition returns the split location.
splitval = A[0]
lessPtr = 1
gtrPtr = N-1
while (lessPtr <= gtrPtr)
while (lessPtr <= gtrPtr and lessPtr < N and A[lessPtr] < splitval) increment lessPtr
while (gtrPtr >= lessPtr and A[gtrPtr] > splitval) decrement gtrPtr
if (lessPtr <= gtrPtr)
if (A[lessPtr] > splitval and A[gtrPtr] < splitval) swap(A[lessPtr], A[gtrPtr])
end while
swap(A[0], A[gtrPtr])
return gtrPtr
End function Partition
Our driver program for this lab will, basically, generate a dataset of a certain size and then call KSmall to find the kth smallest in the dataset.
The final program should do the following:
- Explain its purpose to the user
- Ask the user for the number of numbers.
- Ask the user which index to retrieve. I.e., does the user want the 2nd smallest, the median, or ?
- Generate a single random data set.
- Ask the user if he/she wants the dataset displayed.
- Report the value of the integer in the requested index position.
Top of this page 
Home page 
