Measuring Post–Quickselect Disorder

Authors

Abstract

This paper deals with the amount of disorder that is left in a permutation after one of its elements has been selected with quickselect with or without median-of-three pivoting. Five measures of disorder are considered: inversions, cycles of length less than or equal to some m, cycles of any length, expected cycle length, and the distance to the identity permutation. “Grand averages” for each measure of disorder for a permutation after one of its elements has been selected with quickselect, where 1, 2, . . . , n are the elements being permuted, are computed, as well as more specific results.

Keywords

Volume 3, Issue 2
November 2004
Pages 219-249
  • Receive Date: 23 July 2022
  • Revise Date: 25 May 2024
  • Accept Date: 23 July 2022