Re: bubblesort

From: flapper (nobody_at_a.b.c.dINVALID)
Date: 04/27/04 

Date: Tue, 27 Apr 2004 10:15:18 GMT

Upon seeing that flapper had written:
>>>
>>> The "!" after the call to 'swap' still bothers me, however:
>>>
>>>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).
>>>
Alan Bal jeu remarked:
>
>
> This would be better, stylistically.
>
> bubblesort(List,Sorted) :-
> swap(List,PartSorted),
> bubblesort(PartSorted,Sorted).
>
> swap([X,Y|Tail],[Y,X|Tail]):-
> gt(X,Y), !.
> swap([X,Y|Tail],[X|Rest]) :-
> not( gt(X,Y) ),
> swap([Y|Tail],Rest).
>
>

  That is a nice touch, but it obscures the point I am making.

  (I take it you did not mean to omit the "!" after the call to 'swap'
in the first rule for 'bubblesort' or to omit the second rule altogether.)

  I wrote 'swap' without a "!" in its first rule for a reason, which
was, to emphasize the fact that -- in striking contrast to the elegant
use of "!" which you just now proposed -- the version of 'bubblesort"
that I quoted above is /false/ without the "!" in its first rule. That
is what was bothering me about it: intuituively, it didn't seem possible
to me that a "!" could be /required/ to describe something as simple as
the classical bubblesort algorithm -- which (following
http://www.cc.gatech.edu/people/home/idris/AlgorithmsProject/Search_and_Sort/Basic_Sorts/BubbleSort.html)
I take to be

      Bubblesort (A[n])

        1. for i := 1 to n - 1
        2. do for j := 1 to n - i
        3. do if A[j] > A[j+1]
        4. then temp := A[j]
        5. A[j] := A[j + 1]
        6. A[j + 1 ] := temp

-- but I had never written a bubblesort in Prolog, so I wasn't sure.

  Note that the upper bound on index j decreases by 1 after each of the
(n-1) passes indexed by i. That appears to me to be the signal
difference between what I know as bubblesort, on the one hand, and
either the 'bubblesort' I quoted above or the modified version of it
that you suggested, on the other.

  Hence the definition of bubblesort that I posted and which, in the
interest of intelligibility, I reproduce here:

mybubblesort([],[]).
mybubblesort([X|In],Out) :-
   percolate(X,In,Biggest_Is_Last),
   append_lists(Next,[Biggest],Biggest_Is_Last),
   mybubblesort(Next,Sorted_Minus_Biggest),
   append_lists(Sorted_Minus_Biggest,[Biggest],Out).

percolate(Anything,[],[Anything]).
percolate(Smaller,[Bigger|In],[Smaller|Out]) :-
   gt(Bigger,Smaller),
   percolate(Bigger,In,Out).
percolate(Bigger,[Smaller|In],[Smaller|Out]) :-
   not( gt(Smaller,Bigger) ),
   percolate(Bigger,In,Out).

  I think this is a correct description of the classical bubblesort
algorithm; furthermore, that question aside, it is not only much faster
and capable of sorting larger lists than the so-called 'bubblesort' I
quoted at the outset, it doesn't require any "!"s. 

--
sequitur AT sonic DOT net