- #1

- 807

- 8

## 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 ← 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

while left <= right and A

>= pivot do right ← right – 1

if(left < right) then swap A

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.

Quicksort and partitioning based algorithm.

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!

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!