0
$\begingroup$

I am reading an algorithm book.

Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated for $n$?

$\endgroup$
4
  • 1
    $\begingroup$ any reason you feel you can't create one? $\endgroup$
    – Rinkesh P
    Commented Sep 26, 2022 at 9:33
  • $\begingroup$ @RinkeshP Thank you very much for your comment. I saw decision tree for insertion sort with $n=3$ on p.283 (Fig. 8.23) in "Data Structures and Algorithms" by Aho, Hopcroft and Ullman. But for example I cannot create a decision tree for quicksort since quicksort is complicated. $\endgroup$
    – tchappy ha
    Commented Sep 26, 2022 at 9:46
  • 1
    $\begingroup$ I think you confused the decisions taken by the algorithm with decision tree. While proving the lower bound for sorting we do not care about how the sorting would take place, other than the least no. of comparisons to sort the input. $\endgroup$
    – Rinkesh P
    Commented Sep 26, 2022 at 10:10
  • $\begingroup$ @RinkeshP Thank you very much for your comment. $\endgroup$
    – tchappy ha
    Commented Sep 26, 2022 at 10:52

3 Answers 3

1
$\begingroup$

In general, a decision tree would enumerate all possible permutations $(N!)$ for given input of $N$ elements, out of which only $1$ would be desirable.

A sorting algorithm doesn't generate all possible permutations, it follows a set of predefined steps to reach the desired output. This would be equivalent to taking a path in the decision tree from the root to the leaf which represents the sorted permutation. And if you follow the algorithm, you will always follow the same path.

$\endgroup$
1
  • $\begingroup$ Rinkesh P, Thank you very much for your answer. $\endgroup$
    – tchappy ha
    Commented Sep 26, 2022 at 9:56
2
$\begingroup$

The procedure below can be used to explicitly build the decision tree of any comparison-based algorithm:

  • generate all permutations of the array $[1, 2, \cdots n]$.

  • for every permutation, run the algorithm and note the outcomes of every comparison, together with the involved element indexes.

  • merge the traces so obtained, in the form of a tree.

Below all traces of InsertionSort on four elements:

1≥0 2≥1 3≥2 
1≥0 2≥1 3<2 3≥1 
1≥0 2≥1 3<2 3<1 3≥0 
1≥0 2≥1 3<2 3<1 3<0 
1≥0 2<1 2≥0 3≥2 
1≥0 2<1 2≥0 3<2 3≥1 
1≥0 2<1 2≥0 3<2 3<1 3≥0 
1≥0 2<1 2≥0 3<2 3<1 3<0 
1≥0 2<1 2<0 3≥2 
1≥0 2<1 2<0 3<2 3≥1 
1≥0 2<1 2<0 3<2 3<1 3≥0 
1≥0 2<1 2<0 3<2 3<1 3<0 
1<0 2≥1 3≥2 
1<0 2≥1 3<2 3≥1 
1<0 2≥1 3<2 3<1 3≥0 
1<0 2≥1 3<2 3<1 3<0 
1<0 2<1 2≥0 3≥2 
1<0 2<1 2≥0 3<2 3≥1 
1<0 2<1 2≥0 3<2 3<1 3≥0 
1<0 2<1 2≥0 3<2 3<1 3<0 
1<0 2<1 2<0 3≥2 
1<0 2<1 2<0 3<2 3≥1 
1<0 2<1 2<0 3<2 3<1 3≥0 
1<0 2<1 2<0 3<2 3<1 3<0
$\endgroup$
1
  • $\begingroup$ Yves Daoust, Thank you very much for your answer. $\endgroup$
    – tchappy ha
    Commented Sep 27, 2022 at 13:58
1
$\begingroup$

In theory, yes you should be able to create a decision tree for every comparison based sorting algorithm. You can write a program that will do so (for a fixed comparison-based sorting algorithm of your choice, say quicskort). Do keep in mind that decision trees have n! leaves so (roughly) beyond input sizes of say 11 you will run into storage issues.

Comparison-based sorting is defined rather informally, so to give a complete answer: it may get super complicated to detect whether an algorithm is truly comparison based (even before considering to generate the tree) and there is no formal logic I know of to verify the comparison-based property (would love to find out if someone did it). On the other hand, for most algorithms that are considered in practice the comparison-based property is straightforward to verify, ie quicskort, mergesort and heapsort among several others are easily checked to be comparison based and hence you can produce a decision tree (for small input sizes).

$\endgroup$
5
  • 1
    $\begingroup$ Michel, Thank you very much for your answer. $\endgroup$
    – tchappy ha
    Commented Sep 26, 2022 at 10:52
  • 1
    $\begingroup$ I wonder why you make this discussion about comparison-baseness. In fact, any sorting algorithm can be put in the form of a decision tree. $\endgroup$
    – user16034
    Commented Sep 26, 2022 at 12:48
  • 1
    $\begingroup$ @YvesDaoust what is the "decision tree" of bucket sort? Decision trees are the tool used to represent the computational paths of comparison-based algorithms $\endgroup$ Commented Sep 26, 2022 at 18:44
  • 1
    $\begingroup$ @Michel: you can see that in several ways. First, bucket sort can be implemented with comparisons. Second you can consider that assigning the keys to bucket is a "non-decision process" and the tree is void; but you can very well consider that the choice of a bucket is the outcome of a decision, and you get a $b$-ary tree. That's a matter of convention. $\endgroup$
    – user16034
    Commented Sep 26, 2022 at 19:03
  • 1
    $\begingroup$ Sure. Convention is all well. The aim is to extract useful info on timing. To avail of lower bounds you need to verify the comparison based property even in complex cases, based on a definition of "comparison-based" that is far too informal. Your mileage may differ. $\endgroup$ Commented Sep 26, 2022 at 21:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.