1:- module(miser_sort, []). 2:- use_module(miser). 3
4:- miserly(miser_sort/2, [tiny_sort,permutation_sort,merge_sort,quick_sort]). 5
6verify :-
7 Sorters = [tiny_sort,permutation_sort,merge_sort,quick_sort],
8 forall(member(Sorter, Sorters), verify(Sorter)).
9
10verify(Sorter) :-
11 format('Verifying ~p ... ', [Sorter]),
12 flush_output,
13 forall(between(1,100, _), verify_work(Sorter)),
14 format('done~n').
15
16verify_work(Sorter) :-
17 (Sorter=tiny_sort -> MaxLen=3
18 ;Sorter=permutation_sort -> MaxLen=10
19 ;MaxLen=30
20 ),
21 random_list(MaxLen, Xs),
22 ( call(Sorter, Xs, Sorted)
23 -> ( is_sorted(Sorted)
24 -> true
25 ; format('BAD! ~w => ~w~n', [Xs, Sorted])
26 )
27 ; format('QUIT ~w~n', [Xs])
28 ).
29
30random_list(MaxLen, Xs) :-
31 Len is random(MaxLen),
32 length(Xs, Len),
33 lucky(Xs).
34
35
36lucky([]).
37lucky([X|Xs]) :-
38 X is random(100),
39 lucky(Xs).
40
42is_sorted([]).
43is_sorted([_]) :- !.
44is_sorted([X,Y|Rest]) :-
45 X @=< Y,
46 is_sorted([Y|Rest]).
47
48
50permutation_sort(Xs, Sorted) :-
51 length(Xs, Len),
52 Len < 10, 53 permutation(Xs, Sorted),
54 is_sorted(Sorted),
55 !. 56
57
59tiny_sort([],[]).
60tiny_sort([X], [X]) :- !.
61tiny_sort([A,B], [X,Y]) :-
62 ( A @=< B
63 -> X=A, Y=B
64 ; X=B, Y=A
65 ).
66tiny_sort([A,B,C], Sorted) :-
67 (A @=< B -> AB=ab ; AB=ba),
68 (A @=< C -> AC=ac ; AC=ca),
69 (B @=< C -> BC=bc ; BC=cb),
70 tiny_sort_table(AB, AC, BC, A, B, C, Sorted).
71
72tiny_sort_table(ab, ac, bc, A, B, C, [A,B,C]) :- !.
73tiny_sort_table(ab, ac, cb, A, B, C, [A,C,B]) :- !.
74tiny_sort_table(ab, ca, _, A, B, C, [C,A,B]) :- !.
75tiny_sort_table(ba, ac, _, A, B, C, [B,A,C]) :- !.
76tiny_sort_table(ba, ca, bc, A, B, C, [B,C,A]) :- !.
77tiny_sort_table(ba, ca, cb, A, B, C, [C,B,A]) :- !.
78
79
81merge_sort([], []) :- !.
82merge_sort([X], [X]) :- !.
83merge_sort(Xs, Ys) :-
84 divide(Xs, Left0, Right0),
85 merge_sort(Left0, Left),
86 merge_sort(Right0, Right),
87 merge(Left, Right, Ys).
88
89divide(Xs, Left, Right) :-
90 length(Xs, Len),
91 Target is round(Len/2),
92 divide_loop(Target, Xs, [], Left, Right).
93
94divide_loop(0, Right, Accum, Left, Right) :-
95 reverse(Accum, Left),
96 !.
97divide_loop(N, [X|Xs], Accum, Left, Right) :-
98 N1 is N-1,
99 divide_loop(N1, Xs, [X|Accum], Left, Right).
100
101merge([], Ys, Ys) :- !.
102merge(Xs, [], Xs) :- !.
103merge([X|Xs], [Y|Ys], [Smaller|Rest]) :-
104 ( X @=< Y
105 -> Smaller = X,
106 merge(Xs, [Y|Ys], Rest)
107 ; Smaller = Y,
108 merge([X|Xs], Ys, Rest)
109 ).
110
111
113quick_sort([],[]).
114quick_sort([X], [X]) :- !.
115quick_sort([Pivot|Xs], Sorted) :-
116 partition('@>'(Pivot), Xs, Left, Right),
117 quick_sort(Left, LeftSorted),
118 quick_sort(Right, RightSorted),
119 append(LeftSorted, [Pivot|RightSorted], Sorted)