Finding n-th smallest element in an array

Question

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 about 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.

I find the hint about data structures surprising. The typical algorithm to solve this problem does not require an additional data-structure. — Matthieu M., May 20 '11 at 13:27

Aasmund Eldhuset · Accepted Answer · 2011-05-20T14:53:23.123

16

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).

edited May 20 '11 at 14:53

answered May 20 '11 at 13:14

Aasmund Eldhuset

37,289
4
68
81

3

illustration http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-6-order-statistics-median/ – Andrey Sboev May 20 '11 at 13:18
Ok, your prose helped me to get it (at least better than before). The modification is explained in this PDF: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0125.pdf – Martin Klepsch May 20 '11 at 13:21
Note: the fact that you recurse on only one side (and not both) is the key difference between O(N log N) for sorting and O(log N) for selecting. – Matthieu M. May 20 '11 at 13:23
That clever modification is the BFPRT algorithm, median-of-medians. – Ishtar May 20 '11 at 13:23
Sounds like a neat answer. :) – Chris May 20 '11 at 13:27
@Matthieu M.: True (except I suppose you meant _O(n)_ for selecting). – Aasmund Eldhuset May 20 '11 at 14:50
@Ishtar: I didn't know that - it was lazy of me not to wikipedia (is that a verb?) the abbreviation... – Aasmund Eldhuset May 20 '11 at 14:51
@Aasmund: I did... wish I could edit it :p – Matthieu M. May 20 '11 at 14:51

Christian · Answer 2 · 2011-05-20T13:26:55.730

3

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)

edited May 20 '11 at 13:26

answered May 20 '11 at 13:13

Christian

4,345
5
42
71

I looked at both of your links already. The PowerPoint slides are quite good but I don't understand everything thats written there. Also the described algorithm is the BFPRT algorithm which is, as I understood, only meant to return the median of an array and not the nth-smallest. – Martin Klepsch May 20 '11 at 13:18
@Martin Klepsch - You can easily get the nth smallest item from that algorithm. I will shortly edit my post. – Christian May 20 '11 at 13:23

score 0 · Answer 3 · answered May 20 '11 at 14:54

0

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

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

answered May 20 '11 at 14:54

kuriouscoder

5,394
7
26
40

Finding n-th smallest element in an array

3 Answers3

Linked