Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #164565

Re: **********@b*****.uk

Show all headers | View raw

Richard Damon <Richard@Damon-Family.org> writes:

> On 1/23/22 10:48 AM, Kaz Kylheku wrote:
>
>> On 2022-01-17, Arslan RK <itsarslanfiverr@gmail.com> wrote:
>>
>>> The data in the array may already be in the proper order or
>>> near-proper order, so why make nine passes if fewer will suffice?
>>> Modify the sort to check at the end of each pass if any swaps have
>>> been made.  If none have been made, then the data must already be
>>> in the proper order, so the program should terminate.  If swaps
>>> have been made, then at least one more pass is needed.
>>
>> Your teacher is an ignoramus, or else you are trolling.
>>
>> The above termination test is part of the definition of Bubble Sort.
>>
>> https://en.wikipedia.org/wiki/Bubble_sort
>
> To my knowledge, there is no official legal definition of Bubble
> Sort.  The Naive Sort that doesn't test if it is done still falls
> within what I would consider the family of 'Bubble Sort'.  Checking
> for no swaps, decreasing the bounds each loop by one, or to the last
> swap, are all fairly standard improvements over the naive bubble
> sort.
>
> For a class, starting with the simplest version (with not test)
> and then showing ways to optimize, becomes a very good learning
> experience and gets the students to actually THINK about what is
> happening rather than just copy the algorithm.
>
> Then moving on to other improvements, like cocktails sort reversing
> its pass each time can lead to a natural discussion of algorithms
> and actually designing an algorithm rather than being stuck with
> ones someone gives you.

I agree on all points.  Any algorithm that does repeated swapping
scans may reasonably be called a bubble sort, even the horribly
naive algorithm that starts again from the bottom whenver an out
of order pair is found (and so typically has O( n*n*n ) runtime).
One nice property of bubble sort from an educational perspective
is that, because it is so simple, there are lots of obvious
refinements to try.  Furthermore all the obvious refinements are
still pretty bad performance-wise, which serves as a springboard
into more elaborate but better performing algorithms.

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

Thread

ben.usenet@bsb.me.uk Arslan RK <itsarslanfiverr@gmail.com> - 2022-01-17 10:08 -0800
  Re: ben.usenet@bsb.me.uk scott@slp53.sl.home (Scott Lurndal) - 2022-01-17 18:15 +0000
  Re: ben.usenet@bsb.me.uk Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-17 18:24 +0000
  Re: ben.usenet@bsb.me.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-17 10:45 -0800
  Re: ben.usenet@bsb.me.uk Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 20:43 +0000
    Re: ben.usenet@bsb.me.uk "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-01-17 14:03 -0800
  Re: **********@b*****.uk Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-23 15:48 +0000
    Re: **********@b*****.uk Richard Damon <Richard@Damon-Family.org> - 2022-01-23 13:13 -0500
      Re: **********@b*****.uk Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-23 19:10 -0800
        on legal definitions of a certain algorithm (Was: Re: **********@b*****.uk) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 10:00 -0300
          Re: on legal definitions of a certain algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-30 21:34 +0000
            Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 23:34 -0300
              Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 20:58 -0800
              Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-02-02 11:10 -0300
          Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 21:04 -0800
    Re: **********@b*****.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-23 11:15 -0800
      This newsgroup (Was: for some totally inexplicable reason, **********@b*****.uk) gazelle@shell.xmission.com (Kenny McCormack) - 2022-01-23 20:09 +0000

csiph-web