Understanding Randomized Select algorithm

Question

Here is the algorithm in pseudo code:

Where $A$ is the array to search, $p$ is the starting index in the array, $r$ is the ending index and $i$ represent the number of smaller values we want from our goal value, the $i$ smallest number in the array.

Randomaized select algorithm - pseudocode

I dont understand the $k$.

It gets a value that dont realy represent the index of the value in the original array, but the index value in the sub array we are at, at the recursion process.

Similarly, it doesnt represent the amount of values that are smaller than the pivot we are at, but the number of smaller values in the current sub array in the recursive process.

So how can we check between $i$ and $k$? They dont talk on the same arrays...

Thank you.

• Yuval Filmus: What does the function Randomized-Partition do, and what does it return? Please update the question with this information, without which it is hard to tell what the procedure is doing.
• Yuval Filmus: If you're not sure what's happening, I suggest tracing Randomized-Select on a few sample inputs. The behavior should become apparent.

Answer 1

The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \leq A[q+1],\ldots,A[r]$.

The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A[p],\ldots,A[r]$. To see this, let us assume from now on that all elements of $A$ are distinct (this will slightly simplify the arguments). Then the $q-p$ elements $A[p],\ldots,A[q-1]$ are smaller than $A[q]$, and the rest are larger than $A[q]$.

If $i = k$, then we are done. If $i < k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[p],\ldots,A[q-1]$ (since the $i$th smallest element is smaller than $A[q]$, which is the $k$th smallest element), and moreover, it is the $i$th smallest element in that subarray. If $i > k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[q+1],\ldots,A[r]$ (since the $i$th smallest element is larger than $A[q]$, which is the $k$th smallest element), and moreover, it is that $(i-k)$th smallest element in that subarray (since the $k$ elements $A[p],\ldots,A[q]$ are already smaller than it).