41 lines
1.3 KiB
Text
41 lines
1.3 KiB
Text
|
F partition(&vector, left, right, pivotIndex)
|
|||
|
|
V pivotValue = vector[pivotIndex]
|
|||
|
|
swap(&vector[pivotIndex], &vector[right])
|
|||
|
|
V storeIndex = left
|
|||
|
|
L(i) left .< right
|
|||
|
|
I vector[i] < pivotValue
|
|||
|
|
swap(&vector[storeIndex], &vector[i])
|
|||
|
|
storeIndex++
|
|||
|
|
swap(&vector[right], &vector[storeIndex])
|
|||
|
|
R storeIndex
|
|||
|
|
|
|||
|
|
F _select(&vector, =left, =right, =k)
|
|||
|
|
‘Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive.’
|
|||
|
|
L
|
|||
|
|
V pivotIndex = (left + right) I/ 2
|
|||
|
|
V pivotNewIndex = partition(&vector, left, right, pivotIndex)
|
|||
|
|
V pivotDist = pivotNewIndex - left
|
|||
|
|
I pivotDist == k
|
|||
|
|
R vector[pivotNewIndex]
|
|||
|
|
E I k < pivotDist
|
|||
|
|
right = pivotNewIndex - 1
|
|||
|
|
E
|
|||
|
|
k -= pivotDist + 1
|
|||
|
|
left = pivotNewIndex + 1
|
|||
|
|
|
|||
|
|
F select(&vector, k)
|
|||
|
|
‘
|
|||
|
|
Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1].
|
|||
|
|
left, right default to (0, len(vector) - 1) if omitted
|
|||
|
|
’
|
|||
|
|
V left = 0
|
|||
|
|
V lv1 = vector.len - 1
|
|||
|
|
V right = lv1
|
|||
|
|
assert(!vector.empty & k >= 0, ‘Either null vector or k < 0 ’)
|
|||
|
|
assert(left C 0 .. lv1, ‘left is out of range’)
|
|||
|
|
assert(right C left .. lv1, ‘right is out of range’)
|
|||
|
|
R _select(&vector, left, right, k)
|
|||
|
|
|
|||
|
|
V v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
|
|||
|
|
print((0.<10).map(i -> select(&:v, i)))
|