Randomized selection with tripartitioning

Details Randomized selection with tripartitioning Randomized selection with tripartitioning

2004-01-04

arxiv.org/abs/cs/0401003v1

Computer Science

Data Structures and Algorithms

19 pages

Scientific paper

We show that several versions of Floyd and Rivest's algorithm Select [Comm.\ ACM {\bf 18} (1975) 173] for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average, even when equal elements occur. This parallels our recent analysis of another variant due to Floyd and Rivest [Comm. ACM {\bf 18} (1975) 165--172]. Our computational results suggest that both variants perform well in practice, and may compete with other selection methods, such as Hoare's Find or quickselect with median-of-3 pivots.

Affiliated with

Also associated with

No associations

Rating

Randomized selection with tripartitioning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomized selection with tripartitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized selection with tripartitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113363