K. Kiwiel

activity

20022004

most citedPartitioning schemes for quicksort and quickselect

5 citations · 10 across the 4 of their papers we have counts for

collaborators

Showing 2004Show all

2 papers · 1 filter

cs.DS2004★ 2 cited

Improved randomized selection

Krzysztof C. Kiwiel

We show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$ th smallest of $n$ elements require at most $n + min {k, n - k} + O (n^{1/2} ln^{1/2} n)$ …

cs.DS2004★ 1 cited

Randomized selection with tripartitioning

Krzysztof C. Kiwiel

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\…