Quickselect algorithm: Difference between revisions
→{{header|Mercury}}
Line 2,088:
To more strictly follow the task instructions at the time I am writing this (which call for printing from 1st to 10th ''largest'', in order) I use '''>''' as my ordering predicate. In the generic parts of the code, the predicate is called "Less_than", but '''<''' is simply a conventional name for an ordering predicate. You can read it as meaning "comes before", or "has ordinal less than".
However, the sample vector looks as if it were devised to test finding the kth ''least'' element, so I also run the task with '''<''' as the ordering predicate.
Line 2,182 ⟶ 2,184:
%% quickselect/8 selects the (K+1)th largest element of Arr.
:- pred quickselect(pred(T, T)::pred(in, in) is semidet, int::in,
is det <= urandom(M, io).
quickselect(Less_than, K, Arr0, Arr, Elem, M, !IO) :-
Line 2,260 ⟶ 2,262:
(sfc64.init(P, S)),
make_io_urandom(P, S, M, !IO),
Print_kth_least = (pred(K::in, di, uo) is det -->
print_kth_least(K, example_numbers, M)),
print_line("", !IO),
print_line("In order from greatest to least:", !IO),
print_line("", !IO),
print_line(" nth value", !IO),
foldl(
print_line("", !IO),
print_line("In order from least to greatest:", !IO),
print_line("", !IO),
print_line(" nth value", !IO),
foldl(Print_kth_least, 1 `..` 10, !IO),
print_line("", !IO).
:- pred
M::in, io::di, io::uo)
is det <= urandom(M, io).
(array.from_list(Numbers_list, Arr0)),
Line 2,281 ⟶ 2,290:
quickselect(>, K - 1, Arr0, _, Elem, M, !IO),
format(" %2d %d\n", [i(K), i(Elem)], !IO).
:- pred print_kth_least(int::in, list(int)::in,
M::in, io::di, io::uo)
is det <= urandom(M, io).
print_kth_least(K, Numbers_list, M, !IO) :-
(array.from_list(Numbers_list, Arr0)),
quickselect(<, K - 1, Arr0, _, Elem, M, !IO),
format(" %2d %d\n", [i(K), i(Elem)], !IO).
Line 2,305 ⟶ 2,322:
9 1
10 0
In order from least to greatest:
nth value
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
</pre>
| |||