Finding n-th smallest element in an array [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

How to find the kth largest element in an unsorted array of length n in O(n)?

I'm currently sitting in front of an course assignment. The task is to find the nth-smallest element in an array. (Without sorting it!)

I tried to understand the BFPRT algorithm but from what I got it is only useful if you want to calculate the median and not the "n-th smallest" element.

Another idea I had, was to convert the array into a tree by attaching smaller/bigger nodes to the left/right of the root node. I'm not sure however if this counts as sorting. To accelerate this I could store the number of subnodes in each node.

The complete assignment also includes that the algorithm has to be recursive. There is also the hint to think abou开发者_如何学Pythont other data structures.

What do you think about my idea of transforming the array into a balanced tree?

Are there any other options I might have missed?

EDIT: I looked at various similar questions but were not able to completely understand the answers/apply them to my specific task.

---

The traditional approach to this problem (the order statistic problem) is reminiscent of quicksort. Let's say that you are looking for the k'th smallest element. Pick a (random) pivot element and partition the remaining elements into two groups (without sorting the two groups): L contains all elements that are smaller than or equal to the pivot element (except the pivot element itself), and G contains all elements that are greater than the pivot element. How large is L? If it contains exactly k - 1 elements, then the pivot element must be the k'th smallest element, and you are done. If L contains more than k - 1 elements, then the k'th smallest element must be in L; otherwise, it is in G. Now, apply the same algorithm to either L or G (if you need to use G, you must adjust k since you are no longer looking for the k'th smallest element of G, but the k'th smallest element overall).

This algorithm runs in expected O(n) time; however, there exists a clever modification of the algorithm that guarantees O(n) time in worst case.

Edit: As @Ishtar points out, the "clever modification" is the BFPRT algorithm. Its core idea is to make sure that you never select a bad pivot element, such that the two partitions L and G do not become too unbalanced. As long as one can guarantee that one partition will never be more than c times larger than the other (for some arbitrary, but fixed c), the run time will be O(n).

---

There is a quite complex algorithm that in theory runs in O(n). In practise it is a bit slower. Have a look at this link: link. There is a wikipedia entry about this problem as well: wikilink

EDIT:

A simple pseudocode-algorithm to solve the problem:

k = the k'th element is what we are looking for

FindKthSmallest(Array, k)
pivot = some pivot element of the array. 

L = Set of all elements smaller than pivot in Array
R = Set of all elements greater than pivot in Array

if |L| > k FindKthSmalles(L, k)
else if(|L|+1 == k) return pivot
else return FindKthSmallest(R, k-|L|+1)

---

I love the tournament algorithm here -- it's very intuitive and easy to understand.

http://en.wikipedia.org/wiki/Tournament_selection