Randomized selection with tripartitioning
| dc.creator | Kiwiel, Krzysztof C. | |
| dc.date | 2004-01-04 | |
| dc.date.accessioned | 2026-07-07T03:20:48Z | |
| dc.date.available | 2026-07-07T03:20:48Z | |
| dc.description | 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. | |
| dc.description | 19 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0401003 | |
| dc.identifier | http://arxiv.org/abs/cs/0401003 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31956 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2; G3 | |
| dc.title | Randomized selection with tripartitioning | |
| dc.type | text |