Re: bubblesort

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

  • Next message: Cl?ment: "A new solution to the N-queens problem ?" 
    Date: Sun, 25 Apr 2004 11:51:50 GMT

    flapper wrote:
    > Alan Bal jeu wrote:
    >
    >> "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.
    >>
    >
    > Egad, I forgot the difference between the two -- and somewhere along
    > the way took to calling insertion sort "bubblesort".
    >
    > 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).
    >
    >

    %--------------------------------------------------------------

    % what is sometimes called 'bubblesort':

    swapsort([X1,X2|In],Out) :-
       swap_1st_discordant_pair([X1,X2|In],Next),
       !,
       swapsort(Next,Out).
    swapsort(L,L).

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

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

    %--------------------------------------------------------------

    % what I thought bubblesort meant:

    insertionsort([],[]).
    insertionsort([X1|Rest],Sorted) :-
       insertionsort(Rest,SortedButX1),
       insert(X1,SortedButX1,Sorted).

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

    %--------------------------------------------------------------

    % what I now think bubblesort means:

    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).

    append_lists([],L,L).
    append_lists([X|L1],L2,[X|L3]) :-
       append_lists(L1,L2,L3).

    %--------------------------------------------------------------

    % demo utils

    makelist(0,[]):-!.
    makelist(N,[N|L1]) :-
       N > 0,
       N1 is N - 1,
       makelist(N1,L1).

    rpermute([],[]).
    rpermute([X|Xs],[Y|Ys]) :-
       length([X|Xs],N),
       K1 is random(N), % 0 <= K1 < N
       K is K1 + 1,
       remove_kth(K,[X|Xs],Y,L2),
       rpermute(L2,Ys).

    remove_kth(1,[X1|L1],X1,L1) :- !.
    remove_kth(K,[X1|L1],Xk,[X1|L2]) :-
       K > 1,
       K1 is K - 1,
       remove_kth(K1,L1,Xk,L2).

    run :-
       write('Enter length of list: '),readint(N),nl,
       N > -1,
       makelist(N,Ts),
       write('s[wap] i[nsertion] or b[ubble] sort? '),readchar(T),nl,
       rpermute(Ts,In),
       write('In :'),write(In),nl,
       do_sort(T,In,Out),
       write('Out:'),write(Out),nl.

    readint(N) :- read(N).
    readchar(T) :- read(T).

    do_sort('s',In,Out) :-
       swapsort(In,Out).
    do_sort('i',In,Out) :-
       insertionsort(In,Out).
    do_sort('b',In,Out) :-
       mybubblesort(In,Out).

    %--------------------------------------------------------------

    sequitur AT sonic DOT net

  • Next message: Cl?ment: "A new solution to the N-queens problem ?"

    Relevant Pages

    • Re: Sorting TCollectionItems
      ... in between a bubblesort and an insertion sort, ... Perhaps you need an array of the sorting elements in a ... Then having sorted it you interchange the ...
      (comp.lang.pascal.delphi.misc)
    • Re: sorting algorithms
      ... > And while BubbleSort, CocktailSort Insertion Sort, Binary Insertion Sort, ...
      (comp.programming)
    • Re: A "valid" Bubble sort algorithm?
      ... > Randy wrote: ... >) The way to tell if an algorithm is a bubblesort is: ... >) If yes to both then it's a bubblesort. ... That's still insertion sort. ...
      (comp.programming)
    • Re: bubblesort
      ... Alan Bal jeu wrote: ... >>Would anyone care to comment on ... > Bubblesort is never desirable. ... the tabs seem to have got lost in transmission. ...
      (comp.lang.prolog)