2023-07-01 11:58:00 -04:00
|
|
|
quickselect: function [a k][
|
|
|
|
|
arr: new a
|
|
|
|
|
while ø [
|
|
|
|
|
indx: random 0 (size arr)-1
|
|
|
|
|
pivot: arr\[indx]
|
|
|
|
|
remove 'arr .index indx
|
|
|
|
|
left: select arr 'item -> item<pivot
|
|
|
|
|
right: select arr 'item -> item>pivot
|
|
|
|
|
|
2026-02-01 16:33:20 -08:00
|
|
|
when.has: k [
|
|
|
|
|
[= size left] -> return pivot
|
|
|
|
|
[< size left] -> arr: new left
|
|
|
|
|
true [
|
2023-07-01 11:58:00 -04:00
|
|
|
k: (k - size left) - 1
|
|
|
|
|
arr: new right
|
|
|
|
|
]
|
2026-02-01 16:33:20 -08:00
|
|
|
]
|
2023-07-01 11:58:00 -04:00
|
|
|
]
|
|
|
|
|
]
|
|
|
|
|
|
|
|
|
|
v: [9 8 7 6 5 0 1 2 3 4]
|
|
|
|
|
|
|
|
|
|
print map 0..(size v)-1 'i ->
|
|
|
|
|
quickselect v i
|