1
$\begingroup$

I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). Specifically, a comparison tree is a full binary tree rooted at $s$ where each non-leaf node is labeled with an ordered pair $(x, y)$ such that for any vertex $w$, the path $sw$ contains no pair of vertices $u, v$ so that $u = v$. Each leaf $\lambda$ is labelled with a permutation of $1,2,\dots,n$. The tree satisfies three properties:

  1. Each permutation appears in one of the leaves of the tree.

  2. For each leaf $\lambda$ and each $(x, y)$ occurring in the path $s\lambda$, we have $\lambda_x < \lambda_y$ if the left child of $(x, y)$ occurs in the path, and $\lambda_x > \lambda_y$ if otherwise.

  3. For each leaf $\lambda$ and $\lambda_0 \neq \lambda$, assigning $\lambda_0$ to the leaf $\lambda$ will break the property 2.

By this definition, how many comparison trees are there, as a function of $n$?

Improve this question
$\endgroup$
4
  • $\begingroup$ $\lambda$ denotes a single leaf, and I'm saying that these 3 conditions must hold for all the leafs $\lambda$. A comparative sorting algorithm takes $n$ and an array of size $n$, and I'm saying that all the leafs $\lambda$ are a permutation of that (that also implies that they are the permutation of themselves), and all the permutations of the input array must be covered by the algorithm, that the condition $i)$ requires that. $\endgroup$
    – sbh
    Commented Feb 1 at 6:49
  • $\begingroup$ Thank you. Please check my edit to see whether it accurately reflects your intent. $\endgroup$
    – D.W. ♦
    Commented Feb 1 at 7:07
  • $\begingroup$ $\lambda$ is not necessarily a permutation of $1, 2, ..., n$, as the input is not limited to that. It's okay anyway, as we can make this assumption without causing a change to the answer. $\endgroup$
    – sbh
    Commented Feb 1 at 7:12
  • $\begingroup$ I can see that there need to be $n$ leaves - input nodes? But what is the significance of the root? Does not every input value need to reach one output node? You may be reinventing sorting networks from 2-sorters. $\endgroup$
    – greybeard
    Commented Feb 1 at 8:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.