CODEWITHSUNDEEP
algorithm
Callat
Callat

Reputation: 3044

Meaning of L+k-1 index in Quickselect algorithm

I am studying quickselect for a midterm in my algorithms analysis course and the algorithm I have been working with is the following:

Quickselect(A[L...R],k)
// Input: Array indexed from 0 to n-1 and an index of the kth smallest element
// Output: Value of the kth position 
s = LomutoPartition(A[L...R]) // works by taking the first index and value as the 
                              // pivot and returns it's index in the sorted position
if(s == k-1) // we have our k-th element, it's k-1 because arrays are 0-indexed
    return A[s]
else if(s> L+k-1) // this is my question below 
    Quickselect(L...s-1,k) // basically the element we want is somewhere to the left 
                           // of our pivot so we search that side 
else
    Quickselect(s+1...R, k-1-s) 
    /* the element we want is greater than our pivot so we search the right-side 
     * however if we do we must scale the k-th position accordingly by removing 
     * 1 and s so that the new value will not push the sub array out of bounds 
     */

My question is why in the first if do we need L + k - 1? Doing a few examples on paper I have come to the conclusion that no matter the context L is always an index and that index is always 0. Which does nothing for the algorithm right?

Upvotes: 1

Views: 152

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76297

There seems to be a discrepancy between the line

if(s == k-1)

and the line

else if(s> L+k-1)

The interpretations are incompatible.

As Trincot correctly notes, from the second recursive call on, it's possible that L is not 0. Your Lomuto subroutine doesn't take an array, a low index, and a high index (as the one in Wikipedia does, for example). Instead it just takes an array (which happens to be a subarray between low and hight of some other array). The index s it returns is thus relative to the subarray, and to translate it to the position within the original array, you need to add L. This is consistent with your first line, except that the line following it should read

return A[L + s]

Your second line should therefore also compare to k - 1, not L + k - 1.

Edit

Following the comment, here is the pseudo-code from Wikipedia:

// Returns the n-th smallest element of list within left..right inclusive
// (i.e. left <= n <= right).
// The search space within the array is changing for each round - but the list
// is still the same size. Thus, n does not need to be updated with each round.
function select(list, left, right, n)
    if left = right        // If the list contains only one element,
        return list[left]  // return that element
    pivotIndex  := ...     // select a pivotIndex between left and right,
                        // e.g., left + floor(rand() % (right - left + 1))
    pivotIndex  := partition(list, left, right, pivotIndex)
    // The pivot is in its final sorted position
    if n = pivotIndex
        return list[n]
    else if n < pivotIndex
        return select(list, left, pivotIndex - 1, n)
    else
        return select(list, pivotIndex + 1, right, n)

Note the conditions

        if n = pivotIndex

and

        else if n < pivotIndex

which are consistent in their interpretation of the indexing returned in partitioning.

Once again, it's possible to define the partitioning sub-routine either as returning the index relative to the start of the sub-array, or as returning the index relative to the original array, but there must be consistency in this.

Upvotes: 1

Related Questions