FindKth Algorithm: Solve Homework Problem

  • Thread starter s3a
  • Start date
  • Tags
    Algorithm
In summary, the findKth algorithm takes in an unsorted array of distinct integers and a number k, and returns the k-th smallest element in the array. It uses a partitioning algorithm similar to quickSort and binarySearch to rearrange the elements and find the k-th smallest element in O(n) time. The examples given show how the algorithm works, with the first example finding the smallest element and the second example finding the 4th smallest element.
  • #1
s3a
818
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 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!​
 
Physics news on Phys.org
  • #2
s3a said:
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.
 
  • #3
That makes sense, thanks :).

Now, I just need to figure out this algorithm.
 

FAQ: FindKth Algorithm: Solve Homework Problem

1. What is the FindKth Algorithm?

The FindKth Algorithm is a method used to find the kth smallest element in an unsorted list of numbers. It is commonly used in computer programming and data analysis.

2. How does the FindKth Algorithm work?

The FindKth Algorithm works by dividing the list of numbers into smaller sublists, determining the kth smallest element in each sublist, and then recursively repeating this process until the kth smallest element is found.

3. What is the time complexity of the FindKth Algorithm?

The time complexity of the FindKth Algorithm is O(n), where n is the number of elements in the list. This means that the algorithm has a linear time complexity, making it efficient for large datasets.

4. When should the FindKth Algorithm be used?

The FindKth Algorithm should be used when there is a need to find the kth smallest element in an unsorted list of numbers. It can be useful in various applications such as finding the median or finding the top k elements in a dataset.

5. Are there any limitations to the FindKth Algorithm?

One limitation of the FindKth Algorithm is that it requires the entire list to be stored in memory, which can be a problem for very large datasets. Additionally, the algorithm may not perform well if the list contains duplicate elements or if the kth smallest element is near the beginning or end of the list.

Similar threads

Replies
9
Views
2K
Replies
10
Views
2K
Replies
3
Views
1K
Replies
21
Views
2K
Replies
1
Views
2K
Back
Top