Moves and displacements of particular elements in Quicksort

摘要

In this research note we investigate the number of moves and the displacement of particular elements during the execution of the well-known quicksort algorithm. This type of analysis is useful if the costs of data moves were dependent on the source and target locations, and possibly the moved element itself. From the mathematical point of view, the analysis of these quantities turns out to be related to the analysis of quickselect, a selection algorithm which is a variant of quicksort that finds the i-th smallest element of n given elements, without sorting them. Our results constitute thus a novel application of M. Kuba's machinery [M. Kuba, On quickselect, partial sorting and multiple quickselect, inform. Process. Lett. 99(5) (2006) 181-186] for the solution of general quickselect recurrences.