37 lines
862 B
Plaintext
37 lines
862 B
Plaintext
part := proc(arr, left, right, pivot)
|
|
local val,safe,i:
|
|
val := arr[pivot]:
|
|
arr[pivot], arr[right] := arr[right], arr[pivot]:
|
|
safe := left:
|
|
for i from left to right do
|
|
if arr[i] < val then
|
|
arr[safe], arr[i] := arr[i], arr[safe]:
|
|
safe := safe + 1:
|
|
end if:
|
|
end do:
|
|
arr[right], arr[safe] := arr[safe], arr[right]:
|
|
return safe:
|
|
end proc:
|
|
|
|
quickselect := proc(arr,k)
|
|
local pivot,left,right:
|
|
left,right := 1,numelems(arr):
|
|
while(true)do
|
|
if left = right then return arr[left]: end if:
|
|
pivot := trunc((left+right)/2);
|
|
pivot := part(arr, left, right, pivot):
|
|
if k = pivot then
|
|
return arr[k]:
|
|
elif k < pivot then
|
|
right := pivot-1:
|
|
else
|
|
left := pivot+1:
|
|
end if:
|
|
end do:
|
|
end proc:
|
|
roll := rand(1..20):
|
|
demo := Array([seq(roll(), i=1..20)]);
|
|
map(x->printf("%d ", x), demo):
|
|
print(quickselect(demo,7)):
|
|
print(quickselect(demo,14)):
|