Sorting is a foundational problem in computer science that is typically employed on sequences or total orders. More recently, a more general form of sorting on partially ordered sets (or posets), where some pairs of elements are incomparable, has been studied. General poset sorting algorithms have a lower-bound query complexity of $\Omega(wn + n \log n)$, where $w$ is the width of the poset. We consider the problem of sorting in trees, a particular case of partial orders, and parametrize the complexity with respect to $d$, the maximum degree of an element in the tree, as $d$ is usually much smaller than $w$ in trees. For example, in complete binary trees, $d = \Theta(1), w = \Theta(n)$. We present a randomized algorithm for sorting a tree poset in worst-case expected $O(dn\log n)$ query and time complexity. This improves the previous upper bound of $O(dn \log^2 n)$. Our algorithm is the first to be optimal for bounded-degree trees. We also provide a new lower bound of $\Omega(dn + n \log n)$ for the worst-case query complexity of sorting a tree poset. Finally, we present the first deterministic algorithm for sorting tree posets that has lower total complexity than existing algorithms for sorting general partial orders.
翻译:排序是一个计算机科学的基本问题, 通常在序列或总订单中使用。 最近, 研究了一种比较一般的分类形式, 对部分订购的成套( 或组合) 进行分类, 部分订购的组( 或组合) 中, 部分订购的元素通常比不上一对元素。 普通的 组合排序算法的查询复杂度较低, 即 $\ omega( wn + n\log n) 美元, 美元是配置的宽度。 我们考虑了在树上排序的复杂度问题, 特别是部分订单的复杂度, 并且平衡了 $d$( 美元) 的复杂度, 树上的一个元素的最大程度, 因为$d 通常比树上少得多。 例如, 在完整的二进制树上, $d =\ Theta(1), w =\ Theta( n) $。 我们为最差的树进行随机化的排序算法, 最低的排序也是我们目前最低的排序。