Computing inversion pair cardinality through partition-based sorting |
| |
Authors: | Email author" target="_blank">K?SubramaniEmail author |
| |
Affiliation: | (1) West Virginia University, 749 Engineering Sciences Building, Morgantown, WV, USA |
| |
Abstract: | In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion
pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n · log n) and uses O(n) extra space. The expected time analysis of the new algorithm is different from the analyses existing in the literature,
in that it explicitly uses inversion pairs. The problem of determining the inversion pair cardinality of an array finds applications
in a number of design domains, including but not limited to real-time scheduling and operations research. At the heart of
our algorithm is a new inversion pair conserving partition procedure that is different from existing partition procedures
such as Hoare-partition and Lomuto-partition. Although the algorithm is not fully adaptive, we believe that it is the first
step towards the design of an adaptive, partition-based sorting algorithm whose running time is proportional to the number
of inversion pairs in the input.
|
| |
Keywords: | Partition-based sorting Adaptive Measures of disorder Inversion pairs Randomized algorithm |
本文献已被 SpringerLink 等数据库收录! |
|