Question

Given the array [13, 1, 3, 2, 8, 21, 5, 1] suppose we choose the pivot to be 1 the second element in the array. Which of the following would be valid partitions?

A. 1 [1, 2, 3, 5, 8, 13, 21]
B. 1 [13, 1, 3, 2, 8, 21, 5]
C. 1 [13, 3, 2, 8, 21, 5, 1]
D. [1] 1 [13, 3, 2, 8, 21, 5]
E. [13] 1 [3, 2, 8, 21, 5, 1]
F. [13, 1, 3, 2, 8, 21, 5] 1 2/4

Answer 1

D. [1] 1 [13, 3, 2, 8, 21, 5]

Step-by-step explanation:

Using a quicksort with 1 as the pivot point, elements less than 1 will be sorted to the left of 1 and the other elements are greater than one will be sorted to the right of 1. The order doesn't matter. So we sort [1] to the left of 1 and [13, 3, 2, 8, 21, 5] to the right of 1. So, D. [1] 1 [13, 3, 2, 8, 21, 5] is the valid partition.