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

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
نویسندگان
, ,