Decision tree for Selection-Sort.

Selection-Sort(A)

n = A.length

For j = 1 to n -1 Do

smallest = j

For i = j + 1 to n Do

if A[i] < A[smallest] Then

smallest = i

Exchange A[j] with A[smallest]

(a) Draw the decision tree corresponding to Selection-Sort when running on an array of n = 3 elements A = a1, a2, a3 as in g. 8.1 (keep on the left child and> on the right child). (b) Mark the execution path followed for the array A = 6, 4, 2 (c) For the tree you drew, how many leaves does it have? Compare this with n! and comment on the result.