Quicksort decision tree

Question

I have just spent a couple of hours trying to represent the decision tree for the quicksort algorithm on a set of elements (and I also searched the web). I would like to know what each node actually represents. Is it the comparison between two sets (resulting from the call to Partition)? or just the comparison between two elements of the set? I hope that my question is clear enough.

Answer 1

It depends on what you want to call a decision. Since the only thing that can have different outcome is the choice of pivot element, I think that each edge in your tree is such a choice. A node is thus a partially partitioned array, with marks for the intervals yet to be sorted. In other words, you need a list of pivot indices in addition to the array in each node.