Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: on legal definitions of a certain algorithm Date: Sun, 30 Jan 2022 20:58:45 -0800 Organization: A noiseless patient Spider Lines: 80 Message-ID: <865yq0mrga.fsf@linuxsc.com> References: <20220123074300.987@kylheku.com> <86h79tomko.fsf@linuxsc.com> <86sft55qgd.fsf_-_@levado.to> <87sft4di1w.fsf@bsb.me.uk> <868ruw1vmh.fsf@levado.to> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="5204caba212f86213f2db7ab16b145f8"; logging-data="23662"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+3Jo6hsMMBKAFy8m5ysRdzGwUM/ye24Lg=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:zaR27c2NVeuqnmn7BTu1zu8NUBs= sha1:RgJU372wzMxUH2qct8GZmhn1Zho= Xref: csiph.com comp.lang.c:164745 Meredith Montgomery writes: > Ben Bacarisse writes: > >> Meredith Montgomery 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.