Is this wikipedia code for quickselect incorrect?

user_7101112 0
Viewed 71

I was reading the quickselect algorithm on wikipedia: https://en.wikipedia.org/wiki/Quickselect

  function select(list, left, right, k)
     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 k = pivotIndex
         return list[k]
     else if k < pivotIndex
         return select(list, left, pivotIndex - 1, k)
     else
         return select(list, pivotIndex + 1, right, k - pivotIndex)

Isn't the last recursive call incorrect? I believe it the last argument should just be k rather than k - pivotIndex. Am I missing something here?

algorithm
1 Answers

You are right - the last correction from September 20 introduced this error.

Top comment says that 

// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).

and k is defined over all index range, it is absolute, not relative to local low border, as you noticed in comment.

Aslo checked my implementation of kselect, it uses k in the second call.

user_8444160
Related