ALCOMFT-TR-01-187

Conrado Mart\'\inez, Daniel Panario and Alfredo Viola
Analysis of Quickfind with small subfiles
Barcelona. Work package 4. November 2001.

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.

Postscript file: ALCOMFT-TR-01-187.ps.gz (97 kb).