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

Groups > comp.lang.c > #164745

Re: on legal definitions of a certain algorithm

Show all headers | View raw

Meredith Montgomery <mmontgomery@levado.to> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Meredith Montgomery <mmontgomery@levado.to> writes:
>>
>>>> ["what algorithms may be called bubblesort?"]
>>>
>>> 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 >))

Problem:  what does your algorithm produce if asked to evaluate
an example such as

    (qsort (list 5 5 5 5 5 5 5 5 5))

Disclaimer:  I am guessing at syntax, I don't know Racket.

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

A bad argument and a bad conclusion.  First a sorting algorithm
doesn't have to be an in-place algorithm to have O( n log n )
average case behavior (or even worst case behavior for that
matter).  Second, after correcting for the problem shown above,
and making reasonable assumptions for 'filter' and 'append', the
algorithm shown has the same big-O behavior as an in-place
quicksort.  (There may be a constant factor between them but
that doesn't affect big-O.)  Can you see why?

Disclaimer:  again, I don't know Racket.  It's possible Racket
has some sort of non-linear behavior in places where that isn't
necessary, but that doesn't happen if Racket is "Lisp-ish",
which I am assuming it is.

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