/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   A few sorting algorithms implemented in Prolog
   Written Jan. 17th 2007 by Markus Triska (markus.triska@gmx.at)
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Bubble sort
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

bubblesort(Ls, Bs) :-
    (	append(Front, [A,B|Rest], Ls), A @> B ->
	append(Front, [B,A|Rest], New),
	bubblesort(New, Bs)
    ;	Ls = Bs
    ).

%?- bubblesort([a,b,c,1,5,0,x], Qs).
%@ Qs = [0, 1, 5, a, b, c, x].

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Quicksort

   The well-known and often very slow quicksort.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

quicksort([], []).
quicksort([L|Ls], Qs) :-
    partition(Ls, L, Littles0, Bigs0),
    quicksort(Littles0, Littles),
    quicksort(Bigs0, Bigs),
    append(Littles, [L|Bigs], Qs).

partition([], _, [], []).
partition([L|Ls], Pivot, Littles, Bigs) :-
    (	L @< Pivot ->
	Littles = [L|Rest],
	partition(Ls, Pivot, Rest, Bigs)
    ;	Bigs = [L|Rest],
	partition(Ls, Pivot, Littles, Rest)
    ).

%?- quicksort([a,b,c,1,5,0,x], Qs).
%@ Qs = [0, 1, 5, a, b, c, x].


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Quicksort can also be described using DCGs. This allows for a very
   natural translation of the informal description.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

quicksort([])	  --> [].
quicksort([L|Ls]) -->
    { partition(Ls, L, Littles, Bigs) },
    quicksort(Littles),
    [L],
    quicksort(Bigs).

%?- phrase(quicksort([a,b,c,1,5,0,x]), Qs).
%@ Qs = [0, 1, 5, a, b, c, x].

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Merge sort

   Notice the use of append/3 to split the list.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

mergesort(Ls, Ms) :-
    length(Ls, L),
    (	L =< 1 -> Ms = Ls
    ;	Half is L // 2,
	length(Front0, Half),
	append(Front0, Back0, Ls),
	mergesort(Front0, Front),
	mergesort(Back0, Back),
	merge(Front, Back, Ms)
    ).

% If your Prolog library provides merge/3, comment out the following.

merge([], Ys, Ys) :- !.
merge(Xs, [], Xs) :- !.
merge([X|Xs], [Y|Ys], Ms) :-
    (	X @< Y ->
	Ms = [X|Rest],
	merge(Xs, [Y|Ys], Rest)
    ;	Ms = [Y|Rest],
	merge([X|Xs], Ys, Rest)
    ).

%?- mergesort([a,b,c,1,5,0,x], Ms).
%@ Ms = [0, 1, 5, a, b, c, x].


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Some comparisons
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

% bubble sort, ascending

%?- numlist(1, 3000, Ls), time(bubblesort(Ls,_)).
%@% % 9,001 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)

% descending

%?- numlist(1, 320, Ls0), reverse(Ls0, Ls), time(bubblesort(Ls,_)).
%@% 21,846,117 inferences, 7.47 CPU in 11.63 seconds (64% CPU, 2924514 Lips)


% quicksort, ascending, non-DCG version

%?- numlist(0, 3000, Ls), time(quicksort(Ls, _)).
%@% 18,018,041 inferences, 4.01 CPU in 4.94 seconds (81% CPU, 4493277 Lips)

% ascending, DCG version

%?- numlist(0, 3000, Ls), time(quicksort(Ls, _, _)).
%@% 18,021,006 inferences, 3.94 CPU in 4.61 seconds (85% CPU, 4573859 Lips)

% descending, non-DCG version

%?- numlist(0, 3000, Ls0), reverse(Ls0, Ls), time(quicksort(Ls, _)).
%@% 18,018,041 inferences, 6.47 CPU in 10.12 seconds (64% CPU, 2784860 Lips)

% descending, DCG version

%?- numlist(0, 3000, Ls0), reverse(Ls0, Ls), time(quicksort(Ls, _, [])).
%@% % 13,519,506 inferences, 3.72 CPU in 4.27 seconds (87% CPU, 3634276 Lips)

% merge sort, descending

%?- numlist(0, 3000, Ls0), reverse(Ls0, Ls), time(mergesort(Ls, _)).
%@% 111,748 inferences, 0.03 CPU in 0.04 seconds (84% CPU, 3724933 Lips)