1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: FindKth algorithm

  1. Mar 9, 2012 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    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-
    Output: Returns the k-th smallest element of A[start...stop]

    Write the pseudocode to do this.

    2. Relevant equations
    Quicksort and partitioning based algorithm.

    3. 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!​
  2. jcsd
  3. Mar 9, 2012 #2


    Staff: Mentor

    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.
  4. Mar 9, 2012 #3


    User Avatar

    That makes sense, thanks :).

    Now, I just need to figure out this algorithm.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook