.png){kind=icon}
返回
Computing inversion pair cardinality through partition-based sorting
.png){kind=icon}
PRE
AI
DOI：10.1007/s00607-008-0011-x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
partition-based sorting
adaptive
measures of disorder
inversion pairs
randomized algorithm
期刊
C
IF:
2.8
论文数:
2.3K
被引数:
3.5K
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容