Dog training

« Previous — Next »

BFPRT. they find they

14 August 2008

In computer science, BFPRT (Blum, Floyd, Pratt, Rivest, Tarjan) is a four step algorithm to select the n^th smallest element of an array.

Contents 1 Algorithm 2 Implementation 3 See also 4 References

Algorithm

1. Consider the array as groups of 5 elements. Find the median of each group.
2. Use Select recursively to find x, the median of the medians.
3. Partition the array around x.
4. Let i denote the number of elements on the low side of the partition. If n ≤ i, use Select recursively to find the n^th element of the low side. Otherwise return the n-i^th element of the high side.

Implementation

See also

• Quickselect
• Selection algorithm (Much more detail here.)

References

No comments yet

Leave a Reply

You must be logged in to post a comment.