Abstract:
|
In this paper we investigate the variants of the well-known Hoare's Quickfind algorithm for the selection of the j-th element out of n, when recursion stops for subfiles whose size is below a predefined
threshold and a simpler algorithm is run instead. We provide estimates for the combined number of passes, comparisons and exchanges, for both the basic quickfind and median-of-three quickfind. In each
case, we consider two policies for the small subfiles: insertion sort and selection sort, but the analysis could be easily adapted for alternative policies. We obtain the average cost for each of these variants
and compare them with the costs of standard variants which do not use cutoff. We also give the best explicit cutoff bound for each of the variants. |