Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #397609

Re: Isn't that beauty ? (no it's not)

Show all headers | View raw

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 07 Apr 2026 02:12:49 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>
> <snip>
>
>> My conclusions...
>>
>> The right place to start on sorting algorithms is with bubble
>> sort, not because it's a good algorithm, but because it's the
>> easiest one to show, and what is more important it's a good way
>> to teach about how algorithms evolve.
>
> If you write it in terms of moves rather than in terms of swaps,
> bubble sort is not easier than insertion and selection.

A reason to use swap() is that swap is easier to understand
than moves.  Each swap() operation, all by itself, preserves
the invariant that the array contains the same elements after
the swap() is done that were there before.  With code written
using moves, several statements together need to be looked at
to verify that they are doing the right thing.  Furthermore,
when used in conjunction with follows(), whenever we see the
two together written like this

    if(  follows(x,y,array)  )  swap(x,y,array);

we know that both (1) the array has the same elements as it did
before, and (2) the "sortedness" of array elements has increased,
or at least has remained unchanged.  Compare that to an insertion
sort written using moves, where a whole loop body (including a
'break;' no less), plus a statement after, needs to be examined
to verify that it is doing something sensible.  Clearly less
mental effort is needed to see that the one line written above is
working than what is needed for the eight lines seen in the
insertion sort shown in your (much) earlier posting.

>> There is no reason to use the knuth version of bubble sort.
>> Compared to ordinary bubble sort the upside is small and not
>> worth the downside of needing more intricate code.
>
> knuth version has at least one merit.  You claim that in practice the
> it's too rare that the merit is exercised.  May be, it is true.  Or may
> be cases of almost sorted array with misplaced elements coming in pairs
> with close proximity between peers is not that uncommon.  I don't know.
> But merit exist.

I posted a performance comparison of several sorts including knuth
bubble sort.  It's true that knuth bubble sort is better than plain
bubble sort.  But it's still awful compared to the even simpler
gnome sort.

> OTOH, 'ordinary bubble sort' has no merits at all relatively to simple
> insertion sort.

Simple bubble sort is easier to understand than insertion sort.

For those who don't like bubble sort, there is gnome sort, which
is even simpler than bubble sort, and actually has better
performance.  And, if people will forgive me, it's only a short
leap to get to leaping gnome sort, which has better performance
still.

> BTW, thank you for 'boustrophedon'.  Not that there is a
> serious chance that I will remember the word tomorrow or even
> tonight, But hopefully I'd remember that such word exists.

It comes from Greek, meaning roughly "ox plow turning".  Maybe
that will help you remember;  I think it does for me.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 02:12 -0700
  Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 14:00 +0300
    Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 10:23 -0700
  Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-04-07 16:39 -0400
  Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 11:16 -0700

csiph-web