Question

There is a unique decision tree T for quicksort on five element a_1, a_2, a_3, a_4, a_5. Draw the portion of the tree T showing the path from the root node to the leave node < a_5, a_4, a_3, a_2, a_1 >. For each node, you need to show the comparison made. For each edge, you need to label it with either YES or NO.

Answer 1

To understand quick-sort, let’s look at a high-level description of the algorithm • 1) Divide : If the sequence S has 2 or more elements, select an element x from S to you pivot. Any arbitrary element, like the last, will do. Remove all the elements of S and divide them into 3 sequences: - L, holds S’s elements less than x - E, holds S’s elements equal to x - G, holds S’s elements greater than x • 2) Recurse: Recursively sort L and G • 3) Conquer: Finally, to put elements back into S in order, first inserts the elements of L, then those of E, and those of G. • Here are some pretty diagrams.... sorting 33 Quick-So