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

Groups > comp.lang.c > #164742

Re: on legal definitions of a certain algorithm

Show all headers | View raw

Meredith Montgomery <mmontgomery@levado.to> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Richard Damon <Richard@Damon-Family.org> writes:
>>> On 1/23/22 10:48 AM, Kaz Kylheku wrote:
>
> [...]
>
>>>> 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.  
>
> [...]
>
>> 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).
>
> [...]
>
> This thread is reminding me of an event I went through once.  I took a
> data structures course once and there was a written test that asked me
> to sort a list of numbers using quicksort.  The question was totally
> vague like that.  Sort [a, b, c, d, e] using quicksort.
>
> How did I do it?  First I determined that I was going to use a random
> number generator that was myself --- I chose the pivot-elements so as to
> keep the number of iterations in the algorithm smallest.  (I thought I
> was being elegant that way.)  Then using a functional implementation of
> quicksort in my head --- my favorite ones --- I explained the steps I
> took and how the list was sorted.

Can you sketch the algorithm you used?  I know it's some time ago but I
don't follow what you are saying.  Are you saying that you choose pivot
elements very much not at random, but so as to minimise the work?  That
brings another algorithm into play that is not usually part of a
quicksort.

> I was marked completely off because what I was using ``was not
> quicksort''.  Then the question became what is quicksort.  Effectively
> the teacher claimed quicksort is some imperative implementation of the
> method that runs in O(n log n) on the average case.  (No publication was
> offered to back up this claim.)

Well the O(n log n) bit is not in dispute is it?  Are you saying that
the teacher insisted that quicksort must /not/ be written recursively?
Are you sure you understood?

As a former teacher, I feel somewhat obliged to defend this poor man!
It's certainly possible that he was so ignorant that he thought
quicksort -- one of the most iconic recursive algorithms -- must be
written without recursion, but it seems a stretch, especially as
quicksort is hard to write that way.  You can loop over one "half" of
the recursion, but doing that for both is much more work.

> Upon the teacher's own request, I uselessly showed him various important
> publications that called various versions of quicksort as ``quicksort''
> --- all of which were totally compatiable with my step by step
> illustration of how I sorted the list showed on the test --- without any
> sort of footnote-remark to the effect that they were abusing language or
> something like that.  (Also by his own request, I implemented in the C
> language the version I described on the test.  For the curious, no, I
> did not get any points for the question, despite showing how I could
> implemented the strategy in more than one way in the language
> requested.)

Was a model answer even presented?  Did you get to find out how he
thought quicksort /should/ look?  I'd love to see it!

> I came out of that experience with the conclusion that one cannot
> identify an algorithm with a runtime class.

Hmm.. what's the runtime class got to do with it?  That quicksort "is"
O(n log n) on average (albeit a slightly tricky thing to pin down) was
not in dispute here, was it?  If your algorithm wasn't O(n log n), on
average, then I can see your teacher might have some legitimate
concerns.

-- 
Ben.

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