Bucketing algorithms for sorting, selection and computational geometry
Gary A. Hyslop · 1993
We study bucketing algorithms for sorting, selection, Voronoi diagram construction and the closest pair problem. The performances of Distributive Partitioned Sort (DPS) and Quicksort are compared empirically in a demand paging environment. It is found that DPS requires an amount of real memory approximately equal to 40% to 50% of its image size in order to run faster than Quicksort. The performance of DPS deteriorates rapidly in smaller partitions due to excessive page faulting, while that of Quicksort remains fairly constant. We also investigate the performance of a variant of DPS when the number of buckets is some fraction $\alpha$ of the n items to be sorted. A detailed mathematical analysis of the algorithm is presented to determine the expected number of times each step is executed as a function of n and $\alpha$. Then, an implementation of the algorithm is examined. The experimental running times are used to ascertain typical constants of proportionality. In so doing, the analysis is adjusted to take into account the effect of an address translation buffer. Finally, the value of $\alpha$ which minimizes the running time is determined. We also present a selection algorithm which runs faster than Floyd-Rivest's Select because, while both algorithms use approximately the same number of comparisons, our algorithm uses far fewer data moves (asymptotically zero). Then a method, which is free from numerical errors, is presented for constructing the Voronoi diagram in the plane. The algorithm avoids errors by using only integer arithmetic. It performs fewer computations than a similar algorithm that uses floating point arithmetic and produces a correct diagram even when degeneracies occur. An algorithm is also given for the closest pair problem. Its expected running time is asymptotically O(dn), where d is the dimension of the space and n is the number of points. The running time of the algorithm is much less than that of several other algorithms for the case when d = 2. Finally, we discuss data transformation methods for dealing with non-uniform data distributions. We conclude that further empirical testing is required to determine which methods work best in practice.