% Autor: MB
% Datum: 17.09.2015
% items can be compared by a relation gt(x,y)
gt(X,Y) :- X > Y.  % for present purposes

% 1. Bubblesort
bubblesort( List, Sorted) :-
  swap( List, Listl), !,   % is there anything to swap, do it once here
  sort( Listl, Sorted).    % see if there is more to swap
bubblesort( Sorted, Sorted).    % otherwise we are finished
% we either swap at the beginning of the list or inbetween
swap( [X, Y | Rest], [Y, X | Rest] ) :- gt( X, Y).
swap( [Z | Rest], [Z | Rest1] ) :- swap(Rest, Rest1).

%2. Insertionsort
insertionsort( [], [] ).    % empty list is sorted
insertionsort( [X | Tail], Sorted) :-
  insertionsort( Tail, SortedTail),     % recursively sort the tail
  insert( X, SortedTail, Sorted).       % then insert former head at proper place
insert( X, [Y | Sorted], [Y | Sortedl] ) :-
  gt( X, Y), !,                      % if greater than head of tail the item has to inserted into the tail (recursively)
  insert( X, Sorted, Sortedl).
insert( X, Sorted, [X | Sorted] ).   % a smaller item can just be put in front

%3. Mergesort
mergeLists([],L,L).
mergeLists(L,[],L).
mergeLists([H1|T1],[H2|T2],[H1|T3]):- gT(H2,H1), !,
                                      mergeLists(T1,[H2|T2],T3).
mergeLists([H1|T1],[H2|T2],[H2|T3]):- mergeLists([H1|T1],T2,T3).
                         
split([],[],[]).
split([X],[X],[]).
split([X,Y|Rest],[X|Left],[Y|Right]):- split(Rest,Left,Right).

mergeSort([],[]).
mergeSort([X],[X]).
mergeSort([X,Y],[Y,X]):- gT(X,Y), !.
mergeSort([X,Y],[X,Y]).
mergeSort(List,Sorted):- split(List,Left,Right),
                         mergeSort(Left,SortedLeft),
                         mergeSort(Right,SortedRight),
                         mergeLists(SortedLeft,SortedRight,Sorted), !.
                         
% test: mergeSort([27,2828,1,0,-4,8,34,22,33,456,7,-45,11,234],L).

%4. Quicksort
quicksort([],L - L).
quicksort([Pivot|Tail],A1 - Z)  :-
   pivotSplit(Pivot, Tail, Small, Big),
   quicksort(Small, A1 - [Pivot|A2]),
   quicksort(Big, A2 - Z).

pivotSplit(_, [], [], []).
pivotSplit(Pivot, [Y|Tail], [Y|Small], Big)  :-
   Pivot > Y, !,
   pivotSplit(Pivot, Tail, Small, Big).
pivotSplit(Pivot, [Y|Tail], Small, [Y|Big])  :-
   pivotSplit(Pivot, Tail, Small, Big).