FindKth Algorithm: Solve Homework Problem

[s3a]

Homework Statement

Consider the following problem: Given an unsorted array A[0...n-1] of distinct integers, find the k-th smallest element (with k=0 giving the smallest element). For example, findKth( [ 9 10 6 7 4 12 ] , 0) = 4 and findKth([ 1 7 6 4 15 10 ] , 4 ) = 10.

Complete the following pseudocode for the findKth algorithm. Your algorithm should have similarities to quickSort and to binarySearch and should call the partition algorithm described below which is used by the quickSort method. You can call the partition without redefining it. Your algorithm should have the running time in O(n).

Algorithm partition(A, start, stop)
Input: An array A, indices start and stop.
Output: Returns an index j and rearranges the elements of A for all i < j, A <= A[j] and for all k > i, A[k] >= A[j].

pivot ← A[stop]
left ← start
right ← stop – 1

while left <= right do
while left <= right and A

<= pivot do left ← left + 1
while left <= right and A

>= pivot do right ← right – 1
if(left < right) then swap A

with A

swap A[stop] with A

return left

Algorithm findKth( A, start, stop, k )
Input: An unsorted array A[start...stop] of numbers, and a number k between 0 and stop-
start-1
Output: Returns the k-th smallest element of A[start...stop]

Write the pseudocode to do this.

Homework Equations

Quicksort and partitioning based algorithm.

The Attempt at a Solution

I'm currently stuck at something very simple :(, that is, I don't get the examples for findKth at the top of the question. Like, are those trees or what? And, if they are, how do I know how to make the tree based on the numbers given in between the square brackets?

Any help would be greatly appreciated!
Thanks in advance!​

 

[Mark44]

For example, findKth( [ 9 10 6 7 4 12 ] , 0) = 4 and findKth([ 1 7 6 4 15 10 ] , 4 ) = 10.

If these are the examples you refer to, the first is saying that the 0th smallest element in the list is 4 (i.e., the smallest element). The second is saying that the 4th smallest is 10. Keep in mind that the K in Kth is zero-based, so you can have the 0th smallest, 1st smallest, 2nd smallest, and so on.

 

[s3a]

That makes sense, thanks :).

Now, I just need to figure out this algorithm.