The following is a comparison-based algorithm that sorts in ascending order lists of 3 integers chosen...

Transcribed Image Text:

The following is a comparison-based algorithm that sorts in ascending order lists of 3 integers chosen from the set {0, 1} (e.g. [1,0,0] is a valid input, but [1,2,3] is not) doing only 2 comparisons in the worst case. 1 Function sort3(a): 2 3 4 5 6 7 8 9 if a[2]<a[1] then if a [3] a[1] then swap a [3] and a[1] else swap a [2] and a[1] else if a[3] <a[2] then swap a[3] and a[2] swap a[2] and a[1] a) Draw the decision tree rresponding the algorithm. Write down the permutation corre- sponding to each leaf and which inputs are compatible with each leaf. b) Is the algorithm correct? Use the decision tree to ascertain that. Activate Wir c) Does this contradict the sorting lower bound for comparison-based algorithms? Why? to Settings to The following is a comparison-based algorithm that sorts in ascending order lists of 3 integers chosen from the set {0, 1} (e.g. [1,0,0] is a valid input, but [1,2,3] is not) doing only 2 comparisons in the worst case. 1 Function sort3(a): 2 3 4 5 6 7 8 9 if a[2]<a[1] then if a [3] a[1] then swap a [3] and a[1] else swap a [2] and a[1] else if a[3] <a[2] then swap a[3] and a[2] swap a[2] and a[1] a) Draw the decision tree rresponding the algorithm. Write down the permutation corre- sponding to each leaf and which inputs are compatible with each leaf. b) Is the algorithm correct? Use the decision tree to ascertain that. Activate Wir c) Does this contradict the sorting lower bound for comparison-based algorithms? Why? to Settings to

Answer rating: 100% (QA)

a Decision Tree and Permutations Le... View the full answer