Test on Quicksort

Question 1: In the Lomuto partition scheme, if an element `A[j]` is less than or equal to the pivot `A[high]`, the index `i` is incremented and then `A[i]` is swapped with `A[j]`.

A. Yes

B. No

Explanation: According to the study materials, for the Lomuto partition scheme, if `A[j]` is less than or equal to the pivot `A[high]`, the process is to 'increment `i` and swap `A[i]` with `A[j]`.' This confirms the statement that `i` is incremented before the swap occurs.

Question 2: Consider the array `[5, 2, 8, 1, 9, 3]` to be partitioned using the Lomuto scheme, with the last element (`3`) as the pivot. Following the steps of the Lomuto partition scheme, what is the state of the array after the first element found to be less than or equal to the pivot is processed, including any swaps?

A. [5, 2, 8, 1, 9, 3]

B. [2, 5, 8, 1, 9, 3]

C. [1, 2, 8, 5, 9, 3]

D. [3, 2, 8, 1, 9, 5]

Explanation: The Lomuto partition scheme initializes an index `i` to `low - 1`. It then iterates with `j` from `low` to `high - 1`. The initial array is `[5, 2, 8, 1, 9, 3]`, with pivot `3`. `low = 0`, `high = 5`, so `i = -1`. The first element `A[0]` is `5`. Since `5` is not less than or equal to the pivot `3`, no action is taken. The next element `A[1]` is `2`. Since `2` is less than or equal to the pivot `3`, `i` is incremented to `0`, and `A[i]` (which is `A[0]`, currently `5`) is swapped with `A[j]` (which is `A[1]`, currently `2`). This results in the array `[2, 5, 8, 1, 9, 3]`. This is the first time an element less than or equal to the pivot is processed, leading to a swap.

Question 3: After 'Iteration 3' of the partitioning process described, element '7' is located at index 2 of the array.

A. Yes

B. No

Explanation: After 'Iteration 2', the array is `[2, 7, 1, 6, 8, 5, 3, 4]`, with '7' at index 1. In 'Iteration 3', `A[2]` (which is '1') is found to be ≤ pivot '4'. The `i` pointer increments to 1, and `A[1]` ('7') is swapped with `A[2]` ('1'). Therefore, after 'Iteration 3', the array becomes `[2, 1, 7, 6, 8, 5, 3, 4]`, and '7' is at index 2.

Question 4: After Iteration 5 of the partitioning process, the array state is `[2, 1, 7, 6, 8, 5, 3, 4]`, and then after Iteration 6, the element `A[5]` is swapped.

A. Yes

B. No

Explanation: After Iteration 5, the array is `[2, 1, 7, 6, 8, 5, 3, 4]`. In Iteration 6, `A[5] = 5` is compared to the pivot `4`. Since `5` is not less than or equal to `4`, no swap occurs, and the array remains `[2, 1, 7, 6, 8, 5, 3, 4]`.

Question 5: According to the study materials, what can be observed when visualizing different pivot selection strategies in Quicksort?

A. How choosing the first, last, middle, or a random element affects the initial partition.

B. How choosing a pivot affects the sizes of the resulting sub-arrays.

C. The specific elements that become the pivot in a given array.

D. The number of recursive calls made by the algorithm for each pivot choice.

Explanation: The study materials explicitly state under 'Visualize pivot selection': 'You can see how choosing the first, last, middle, or a random element affects the initial partition and the sizes of the resulting sub-arrays.' This directly covers options 0 and 1. Option 2 is incorrect because while simulations demonstrate pivot selection, the material doesn't specify 'the specific elements that become the pivot' as an observation point, rather it lists types of elements (first, last, etc.) that *can* be chosen. Option 3 is incorrect because 'tracking recursive calls' is a separate observational point, not directly tied to visualizing pivot selection strategies alone.