Fast Deterministic Selection Andrei Alexandrescu June 2016 (1606.00484v1) 计算

Fast Deterministic SelectionAndrei Alexandrescu The D Language Foundationandrei@erdani.comAbstract The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than sim- ple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection al- gorithm QUICKSELECTADAPTIVE based on a refined def- inition of MEDIANOFMEDIANS. The algorithm’s perfor- m