Question

Suppose we use RANDOMIZED-SELECT to select the minimum element of the array A = {12, 0, 4, 3, 5, 7, 9, 2, 8, 11}. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZEDSELECT.

Answer 1

Q.Suppose we use RANDOMIZED-SELECT to select the minimum element of the array A = {12, 0, 4, 3, 5, 7, 9, 2, 8, 11}. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZEDSELECT.

Answer:

In the example, the sequence would be{ 12,11,9,8,7,5,4,3,2,0 }

• pivot 12 { 0,4,3,5,7,9,2,8,11}
• pivot 11 {0,4,3,5,7,9,2,8}
• pivot 9 {0,4,3,5,7,2,8}
• pivot 8 {0, 4, 3, 5,7,2 }
• pivot 7 {0, 4, 3, 5, 2}
• pivot 5 {0, 4, 3, 2}
• pivot 4 {0, 3, 2}
• pivot 3 {0, 2}
• pivot 2 {0}
• return 0