1.Previous
3.Next

with a loop:

function select(list, left, right, k) is loop if left = right then return list[left] pivotIndex := ... // select pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex then return list[k] else if k < pivotIndex then right := pivotIndex - 1 else left := pivotIndex + 1This select function works only with the Lomuto partition scheme. This is because select assumes that the return value from partition is the position of the pivot. This is true for the Lomuto partition scheme, but not for the Hoare's partition scheme. In Hoare's scheme, the return value is the last index of the "left" partition, and the pivot is not guaranteed to be "in between" the partitions.

1.Previous
3.Next