bubblesort

From: flapper (not_at_a.b.c.dINVALID)
Date: 04/24/04 

Date: Fri, 23 Apr 2004 23:31:11 GMT

Would anyone care to comment on
the relative advantages/disadvantages
and/or desirability/undesirability of
the two versions of bubblesort shown below?

% from <3c149ade.0404220140.648c07ab@posting.google.com>:

bubblesort(List,Sorted) :-
        swap(List,PartSorted),!,
        bubblesort(PartSorted,Sorted).
bubblesort(L,L).

swap([X,Y|Tail],[Y,X|Tail]):-
        gt(X,Y).
swap([X,Y|Tail],[X|Rest]) :-
        not( gt(X,Y) ),
        swap([Y|Tail],Rest).

% my simple-minded bubblesort:

mybubblesort([],[]).
mybubblesort([X|L],Sorted) :-
        mybubblesort(L,L1),
        percolate(X,L1,Sorted).

percolate(CurrBubble,[],[CurrBubble]).
percolate(CurrBubble,[X|L],[CurrBubble,X|L]) :-
        not( gt(CurrBubble,X) ).
percolate(CurrBubble,[X|L1],[X|L2]) :-
        gt(CurrBubble,X),
        percolate(CurrBubble,L1,L2).

gt(X,Y):- Y @< X. 

--
sequitur AT sonic DOT net