Bubble sort in Prolog language

I must implement the bubble开发者_StackOverflow sort function (the sorting algorithm).

I have already implemented bubblesort and swap, a help function for bubblesort:

swap([X,Y|T1],[Y,X|T1]):-(Y<X,!).
swap([X|T1],[X|T2]):- swap(T1,T2).

bubblesort([],[]) :- !.
bubblesort(T1,T2) :- (bubblesort(swap(T1,T2),T2)).

I get an infinite loop. I must keep the signature of the function:

bubblesort(T1,T2)

I'm stuck on this question for 2 hours. Does anyone have an idea how I can do that?

Until there is no change in swap procedure, keep swapping. If there was no change in swap then you have sorted list.

bubblesort ( List, SortedList) :-
    swap ( List, List1 ), ! ,
    bubblesort ( List1, SortedList) .
bubblesort ( List, List).

swap ( [ X, Y | Rest ], [ Y, X | Rest ] ) :-
    X > Y, ! .
swap ( [ Z | Rest ], [ Z | Rest1 ] ) : -
    swap (Rest, Rest1 ).

The simple bubble sort algorithm is made up of two main loops:

1. Traverse the list, 'swapping' each pair of elements if they are not 'in order' (inner loop).
2. Repeat (1) on the result until the list is completely sorted (outer loop).

The inner loop (1) can be expressed like this:

% performs a single pass of a bubble-sort on a list
do_bubble_sort([], []).
do_bubble_sort([X], [X]).
do_bubble_sort([X0,X1|Xs], [X0|Rem]) :-
    X0 =< X1, !,
    do_bubble_sort([X1|Xs], Rem).
do_bubble_sort([X0,X1|Xs], [X1|Rem]) :-
    do_bubble_sort([X0|Xs], Rem).

do_bubble_sort/2 above takes a list, and recursively swaps consecutive elements along the list if they don't satisfy the =< test (3rd clause). This inner loop is then called by the outer loop predicate, bubble_sort/2, as shown below:

% repeatedly performs a bubble sort on a list until it is sorted
bubble_sort(L, SL) :-
    do_bubble_sort(L, L0),
    (sorted_order(L0) ->
        SL = L0
    ;   bubble_sort(L0, SL)
    ).

This predicate takes the input list and recursively applies do_bubble_sort/2 until the predicate sorted_order/1 succeeds on the result, i.e., if the list is eventually sorted. sorted_order/1 can be defined like this:

% checks a list of things are in sorted (ascending) order
sorted_order([]).
sorted_order([_]) :- !.
sorted_order([X0,X1|R]) :-
    X0 =< X1,
    sorted_order([X1|R]).

This predicate takes a list and recursively checks that each pair of consecutive elements are in sorted order (by way of the =< test, just as we're using in do_bubble_sort/2 - this is important, otherwise the algorithm mightn't terminate!)

It almost hurts to write something so inefficient:

bubblesort(L, L1) :-
        (   bubble(L, L2)
        ->  bubblesort(L2, L1)
        ;   L = L1 ).

bubble([A, B|T], L) :-
        (   A > B
        ->  L = [B, A|T]
        ;   L = [A | L1],
            bubble([B|T], L1)).

:- bubblesort([2,4,2,3, 2, 6,6,3,1, 11, 2, 3, 1], Out).

The problem was caused by recursive querying. When querying bubblesort(T1, T2), it queries bubblesort(swap(T1, T2), T2), then, by second clause of bubblesort/2, bubblesort(swap(swap(T1, T2), T2'), T2) and T2 is unified as T2, and then loop. It never get the first result of swap(T1, T2) query.

bubbleSort(InputList,SortList):-swap(InputList,List),
                                 !,
                                 printList(List),
                                 bubbleSort(List,SortList).
bubbleSort(SortList,SortList).

swap([X,Y|T],[Y,X|T]):-X>Y.
swap([Z|T],[Z|T1]):-swap(T,T1).

printList([]):-nl.
printList([Head|List]):-write(Head),
                        write(' '),
                        printList(List).

bubblesort ( List, SortedList) :-
    swap ( List, List1 ), ! ,
    bubblesort ( List1, SortedList) .
bubblesort ( List, List).