Pivot Index After One Quicksort Partition of [76, 97, 25, 115, 83, 51, 18, 36]

An online assessment includes this multiple-choice question. A quicksort implementation uses the first element of the current subarray as its pivot. It runs one partition step on the array `[76, 97, 25, 115, 83, 51, 18, 36]` Using 1-based indexing, at what index is the pivot once the partition step is complete? - **A.** 1 - **B.** 3 - **C.** 4 - **D.** 5 Choose one option and show how you know. ```hint Skip the swaps Ask what must be true of every element to the left of the pivot once partitioning is done. ``` ```hint Count the base Check whether the number you arrive at is a 0-based or a 1-based position. ``` ### Clarifying Questions - Does the partition routine finish by moving the pivot into its final sorted position, or is it Hoare's original scheme, which only splits the array into two parts? - How does the routine treat elements equal to the pivot? - Is this the first partition step, run on the whole array before any recursive call? ### What a Strong Answer Covers - The correct option, justified by the partition invariant rather than by guessing - A correct element-by-element trace of one concrete partition scheme - The 1-based versus 0-based distinction, and why each wrong option is tempting - Awareness that the answer assumes a scheme that places the pivot, and how equal keys or Hoare's scheme change the outcome ### Follow-up Questions - Write out the whole array after the partition step for the scheme you traced. - If the array contained a second 76, at which indices could the pivot end up? - Under Hoare's original scheme, where does 76 end up for this array, and what index does the routine return? - If the same first-element pivot rule is used on an array that is already sorted, how long does the whole sort take, and how would you change the pivot choice?