Re: bubblesort

From: Alan Bal jeu (jeu_at_sympatico.deleteme.ca)
Date: 04/24/04 

Date: Fri, 23 Apr 2004 21:02:45 -0400

"flapper" <not@a.b.c.dINVALID> wrote in message
news:3Hhic.7814$Fo4.97117@typhoon.sonic.net...
> Would anyone care to comment on
> the relative advantages/disadvantages
> and/or desirability/undesirability of
> the two versions of bubblesort shown below?

Bubblesort is never desirable.
In fact though, the second algorithm looks like insertion sort,
which is better than bubblesort.

As to style, both are hard to read due to lack of indentation.
All stuff following the :- should be indented a few spaces so
one can see where the predicates start and stop easier.

>
> % 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