TY - GEN A1 - Kiwiel, Krzysztof PB - Instytut Badań Systemowych. Polska Akademia Nauk PB - Systems Research Institute. Polish Academy of Sciences N1 - 21 pages ; 21 cm N1 - Bibliography p. 19-21 N2 - It has been shown that several versions of Floyd and Rivest’s algorithm SELECT for finding the kth smallest of n elements require at most n+min{k, n-k} + o(n) comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. The obtained computational results confirm that SELECT may be the best algorithm in practice. L1 - http://www.rcin.org.pl/Content/139518/PDF/RB-2003-69.pdf M3 - Text CY - Warszawa J2 - Raport Badawczy = Research Report ; RB/69/2003 PY - 2003 KW - Medians KW - Computational complexity KW - Partitioning KW - Selection KW - Mediana KW - Selekcja KW - Partycjonowanie KW - Złożoność obliczeniowa T1 - Randomized Selection with Quintary Partitions UR - http://www.rcin.org.pl/dlibra/publication/edition/139518 ER -