کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430607 | 688061 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tight bounds for online stable sorting
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Although many authors have considered how many ternary comparisons it takes to sort a multiset S of size n, the best known upper and lower bounds still differ by a term linear in n . In this paper we restrict our attention to online stable sorting and prove upper and lower bounds that are within o(n)o(n) not only of each other but also of the best known upper bound for offline sorting. Specifically, we first prove that if the number of distinct elements σ=o(n/logn), then (H+1)n+o(n)(H+1)n+o(n) comparisons are sufficient, where H is the entropy of the distribution of the elements in S . We then give a simple proof that (H+1)n−o(n)(H+1)n−o(n) comparisons are necessary in the worst case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 2, June 2011, Pages 176–181
Journal: Journal of Discrete Algorithms - Volume 9, Issue 2, June 2011, Pages 176–181
نویسندگان
Travis Gagie, Yakov Nekrich,