Volume 3, Issue 2 (November 2004)                   JIRSS 2004, 3(2): 219-249 | Back to browse issues page

XML Persian Abstract Print


Abstract:   (6314 Views)
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.
Full-Text [PDF 255 kb]   (1803 Downloads)    
Subject: 60: Probability theory and stochastic processes
Received: 2011/08/26 | Accepted: 2015/09/12