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
   41% true if elements of Xs are sorted in increasing order
   42is_sorted([]).
   43is_sorted([_]) :- !.
   44is_sorted([X,Y|Rest]) :-
   45    X @=< Y,
   46    is_sorted([Y|Rest]).
   47
   48
   49% test every permutation of Xs looking for one that's sorted
   50permutation_sort(Xs, Sorted) :-
   51    length(Xs, Len),
   52    Len < 10,   % takes too long on longer lists
   53    permutation(Xs, Sorted),
   54    is_sorted(Sorted),
   55    !.  % only want the first sorted permutation
   56
   57
   58% hardcoded sort for tiny lists
   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
   80% traditional merge sort
   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
  112% standard quick sort
  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)