Sorting algorithms/Heapsort: Difference between revisions
→{{header|NetRexx}}
m (→{{header|Quackery}}: typo) |
|||
Line 3,694:
#(0, 1, 1, 2, 4, 5, 5, 6, 6, 7)
</lang>
=={{header|Mercury}}==
{{works with|Mercury|22.01.1}}
<lang mercury>%%%-------------------------------------------------------------------
:- module heapsort_task.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module array.
:- import_module int.
:- import_module list.
:- import_module random.
:- import_module random.sfc16.
%%%-------------------------------------------------------------------
%%%
%%% heapsort/3 --
%%%
%%% A generic heapsort predicate. It takes a "Less_than" predicate to
%%% determine the order of the sort.
%%%
%%% That I call the predicate "Less_than" does not, by any means,
%%% preclude a descending order. This "Less_than" refers to the
%%% ordinals of the sequence. In other words, it means "comes before".
%%%
%%% The implementation closely follows the task pseudocode--although,
%%% of course, loops have been turned into tail recursions and arrays
%%% are treated as state variables.
%%%
:- pred heapsort(pred(T, T)::pred(in, in) is semidet,
array(T)::array_di, array(T)::array_uo) is det.
heapsort(Less_than, !Arr) :-
heapsort(Less_than, size(!.Arr), !Arr).
:- pred heapsort(pred(T, T)::pred(in, in) is semidet, int::in,
array(T)::array_di, array(T)::array_uo) is det.
heapsort(Less_than, Count, !Arr) :-
heapify(Less_than, Count, !Arr),
heapsort_loop(Less_than, Count, Count - 1, !Arr).
:- pred heapsort_loop(pred(T, T)::pred(in, in) is semidet,
int::in, int::in,
array(T)::array_di, array(T)::array_uo) is det.
heapsort_loop(Less_than, Count, End, !Arr) :-
if (End = 0) then true
else (swap(End, 0, !Arr),
sift_down(Less_than, 0, End - 1, !Arr),
heapsort_loop(Less_than, Count, End - 1, !Arr)).
:- pred heapify(pred(T, T)::pred(in, in) is semidet, int::in,
array(T)::array_di, array(T)::array_uo) is det.
heapify(Less_than, Count, !Arr) :-
heapify(Less_than, Count, (Count - 2) // 2, !Arr).
:- pred heapify(pred(T, T)::pred(in, in) is semidet,
int::in, int::in,
array(T)::array_di, array(T)::array_uo) is det.
heapify(Less_than, Count, Start, !Arr) :-
if (Start = -1) then true
else (sift_down(Less_than, Start, Count - 1, !Arr),
heapify(Less_than, Count, Start - 1, !Arr)).
:- pred sift_down(pred(T, T)::pred(in, in) is semidet,
int::in, int::in,
array(T)::array_di, array(T)::array_uo) is det.
sift_down(Less_than, Root, End, !Arr) :-
if (End < (Root * 2) + 1) then true
else (locate_child(Less_than, Root, End, !.Arr, Child),
(if not Less_than(!.Arr^elem(Root), !.Arr^elem(Child))
then true
else (swap(Root, Child, !Arr),
sift_down(Less_than, Child, End, !Arr)))).
:- pred locate_child(pred(T, T)::pred(in, in) is semidet,
int::in, int::in,
array(T)::in, int::out) is det.
locate_child(Less_than, Root, End, Arr, Child) :-
Child0 = (Root * 2) + 1,
(if (End =< Child0 + 1)
then (Child = Child0)
else if not Less_than(Arr^elem(Child0), Arr^elem(Child0 + 1))
then (Child = Child0)
else (Child = Child0 + 1)).
%%%-------------------------------------------------------------------
main(!IO) :-
R = (sfc16.init),
make_io_random(R, M, !IO),
Generate = (pred(Index::in, Number::out, IO1::di, IO::uo) is det :-
uniform_int_in_range(M, min(0, Index), 10, Number,
IO1, IO)),
generate_foldl(30, Generate, Arr0, !IO),
print_line(Arr0, !IO),
heapsort(<, Arr0, Arr1),
print_line(Arr1, !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</lang>
{{out}}
<pre>$ mmc heapsort_task.m && ./heapsort_task
array([3, 9, 3, 8, 5, 7, 0, 7, 3, 9, 5, 0, 1, 2, 0, 5, 8, 0, 8, 3, 8, 2, 6, 6, 8, 5, 7, 6, 5, 7])
array([0, 0, 0, 0, 1, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9])</pre>
=={{header|NetRexx}}==
| |||