作者
Amr Elmasry
发表日期
2002/6/25
图书
International Colloquium on Automata, Languages, and Programming
页码范围
183-194
出版商
Springer Berlin Heidelberg
简介
We introduce Binomialsort, an adaptive sorting algorithm that is optimal with respect to the number of inversions. The number of comparisons performed by Binomialsort, on an input sequence of length n that has I inversions, is at most 2nlogI/n + O(n) [1]. The bound on the number of comparisons is further reduced to 1.89nlogI/n + O(n) by using a new structure, which we call trinomial queues. The fact that the algorithm is simple and relies on fairly simple structures makes it a good candidate in practice.
学术搜索中的文章
A Elmasry - International Colloquium on Automata, Languages …, 2002