20 lines
584 B
Plaintext
20 lines
584 B
Plaintext
|
qselect(xs,k) =
|
||
|
|
~xs -> {
|
||
|
|
pivot <- xs[0]!
|
||
|
|
left <- xs[#0 <= pivot]
|
||
|
|
right <- xs[#0 > pivot]
|
||
|
|
} ->
|
||
|
|
if k > |left| + 1 then qselect(right, k - |left| - 1)
|
||
|
|
else if k == |left| + 1 then [pivot]
|
||
|
|
else qselect(left, k);
|
||
|
|
|
||
|
|
_search(xs, k) =
|
||
|
|
if xs[1] == k then xs
|
||
|
|
else if xs[1] > k then _search(xs[0], k)
|
||
|
|
else _search(xs[2], k);
|
||
|
|
|
||
|
|
sorted(xs) = sorted(xs[0]) ++ [xs[1]] ++ sorted(xs[2]);
|
||
|
|
search(xs, k) = |_search(xs, k)| != 0;
|
||
|
|
insert(xs, k) = _insert(k, _search(xs, k));
|
||
|
|
_insert(k, xs) = if |xs| == 0 then xs << [] << k << [] else xs
|