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

Groups > comp.lang.c > #164743

Re: on legal definitions of a certain algorithm

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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 used exactly this one.  This is Racket syntax.  (I'm sure you can see
the meaning the procedure /random-element-of/.  And, of course, to sort
a list using such algorithm I will have to be the random generator
myself.  I wasn't going to flip coins during the test.)

(define (qsort ls)
  (cond [(empty? ls) empty]
  [else
    (let ([pivot (random-element-of ls)])
      (append (qsort (smaller pivot ls))
              (list pivot)
              (qsort (greater pivot ls))))]))

(define (make-filter cmp)
  (lambda (pivot ls)
     (cond [(empty? ls) empty]
           [else
             (filter (lambda (x) (cmp x pivot)) ls)])))

(define smaller (make-filter <))
(define greater (make-filter >))

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

Yes.  I chose the numbers myself.  This was not his issue at all.  I had
to ``run an algorithm on paper'', so I had to somehow choose pivot
elements.  I could have chosen always the first element or always the
last.  I decided to choose it ``at random''.  It was a paper test, so
shortening the answer was definitely an elegant thing to do.  (It was an
illustration that I knew what I was doing --- because I knew the choices
that minimized the number of steps.)

His problem was the algorithm I followed was a functional one and the he
apparently was unable to accept that could be called quicksort.  His
final argument was that the complexity was not the same --- that was his
evidence that what I executed was not 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?

Recursion was not the problem.  The problem is that that version above
is not O(n log n) because the sorting is not in-place.

> Are you sure you understood?

I would never claim I'm sure about understanding someone like that.  He
demanded I showed how to write the algorithm and show references of
other people saying it was quicksort and so on.  I showed a few serious
publications calling it quicksort.  (I still have those references.)  I
did not demand anything of him.  I take no pleasure in seeing people not
able to explain themselves.  It was clear he was not well informed on
the subject.

What he was looking for was the algorithm below --- or something very
close to this.  He did not want anyone to write the method down; he
wanted students to just sort a list of numbers.

This is Python, so let A be a list so that the sorting happens
/in-place/.

def qsort(A, lo, hi):
  if lo < hi:
    p = partition(A, lo, hi)
    qsort(A, lo, p)
    qsort(A, p + 1, hi)
    return A

def partition(A, lo, hi):
  pivot = A[lo]
  i = lo - 1
  j = hi + 1
  while True:
    while True:
      i = i + 1
      if A[i] >= pivot:
        break
  while True:
    j = j - 1
    if A[j] <= pivot:
      break
    if i >= j:
      return j
  A[i], A[j] = A[j], A[i]

> As a former teacher, I feel somewhat obliged to defend this poor man!

He needs an exceptional defense!

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

I had a feeling his problem was with functional programming.  He seemed
to think it was impossible to call anything quicksort that did not sort
in place.

>> 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?  

Yes.  On the board I remember seeing various lines with numbers written
horizontally, clearly showing that he was thinking of an in-place
sorting.  Each line was an iteration.

> Did you get to find out how he thought quicksort /should/ look?  I'd
> love to see it!

Yes, that version above would be what he would have in mind.  I
understood he had one version of quicksort in mind and it had to be that
one he had in mind.

>> 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?  

Nothing.  He was the one that said --- this is not O(n log n) and so I
can't accept 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.

I don't know the O-expression of the complexity of that Racket qsort
procedure above.  I think I'd have to look up the master theorem to try
to tell it.  I bet you can apply the theorem from the top of your mind.
If it is not O(n log n), then that was the teacher's argument.

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