Quickselect algorithm: Difference between revisions
Added 11l
(Added Wren) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 8:
* Note: Quick''sort'' has a separate [[Sorting algorithms/Quicksort|task]]. <br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>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)))</lang>
{{out}}
<pre>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|ALGOL 68}}==
| |||