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

Groups > comp.lang.c > #164449 > unrolled thread

ben.usenet@bsb.me.uk

Back to article view | Back to comp.lang.c

Contents

  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

#164449 — ben.usenet@bsb.me.uk

I want some help.
if anyone is reading please contact
The bubble sort presented in for large arrays. Make the following simple modifications to
improve
the performance of the bubble sort:
b) 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.
1. Devise an Algorithm
2. Create a program in C++

[toc] | [next] | [standalone]

#164450

Arslan RK <itsarslanfiverr@gmail.com> writes:
>I want some help.
>if anyone is reading please contact
>The bubble sort presented in for large arrays. Make the following simple modifications to
>improve
>the performance of the bubble sort:
>b) 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.
>1. Devise an Algorithm
>2. Create a program in C++

Sleeping in class, it seems.

[toc] | [prev] | [next] | [standalone]

#164451

On Mon, 17 Jan 2022 10:08:10 -0800, Arslan RK wrote:

> I want some help.
> if anyone is reading please contact
> The bubble sort presented in for large arrays. Make the following simple modifications to
> improve
> the performance of the bubble sort:
> b) 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.
> 1. Devise an Algorithm
> 2. Create a program in C++

First off, you posted your request to the wrong usenet newsgroup.
This is comp.lang.c, where we discuss programming in the C programming
language. You want a C++ solution, and thus should post your questions
to comp.lang.c++.

If you use google groups to post, you will have difficulty posting to
comp.lang.c++, as the Google interface has glitches that prevent posting
to that newsgroup. If that is the case, then I suggest that you use a
different news source; eternal-september.org, and aioe.org both offer
free usenet access.


Secondly, if you are having problems, we can only help you if you show
us your work. Are you having problems understanding the requirements,
or with your code?

-- 
Lew Pitcher
"In Skills, We Trust"

[toc] | [prev] | [next] | [standalone]

#164452

On Monday, 17 January 2022 at 18:08:20 UTC, itsarsl...@gmail.com wrote:
> I want some help. 
> if anyone is reading please contact 
> The bubble sort presented in for large arrays. Make the following simple modifications to 
> improve 
> the performance of the bubble sort: 
> b) 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. 
> 1. Devise an Algorithm 
> 2. Create a program in C++
>
Usenet isn't a free homework doing service, and I hope that no-one will post
a solution you can dishonestly submit as your own work.

If you post an attempt and have some specific question about it, that's
different.

[toc] | [prev] | [next] | [standalone]

#164453

Arslan RK <itsarslanfiverr@gmail.com> writes:

> I want some help.

Why did you start a thread with my email address as the subject line?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#164458

On 1/17/2022 12:43 PM, Ben Bacarisse wrote:
> Arslan RK <itsarslanfiverr@gmail.com> writes:
> 
>> I want some help.
> 
> Why did you start a thread with my email address as the subject line?
> 

No shit!

[toc] | [prev] | [next] | [standalone]

#164552 — Re: **********@b*****.uk

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

[toc] | [prev] | [next] | [standalone]

#164555 — Re: **********@b*****.uk

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.

[toc] | [prev] | [next] | [standalone]

#164565 — Re: **********@b*****.uk

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.

[toc] | [prev] | [next] | [standalone]

#164733 — on legal definitions of a certain algorithm (Was: Re: **********@b*****.uk)

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.

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

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

I came out of that experience with the conclusion that one cannot
identify an algorithm with a runtime class.  A functional language is
able to imitate an imperative one with a maximum loss of O(ln n) steps.
For example, given an algorithm that runs in O(n) time, the same
algorithm can be implemented in a functional machine in time O(n ln n).
That's theorem 3.1 of the following paper.

--8<---------------cut here---------------start------------->8---
Nicholas Pippenger. “Pure versus impure Lisp”. Em: ACM Transactions on
Programming Languages and Systems (TOPLAS) 19.2 (1997), pp. 223–238.
--8<---------------cut here---------------end--------------->8---

In the context of where we were --- English-language descriptions of
algorithms ---, there was no possibility for the distinction of
algorithms by way of their expressions.  Not even the typical
programming language is able to do that, much less English.  The paper
below makes that point.

--8<---------------cut here---------------start------------->8---
Andreas Blass, Nachum Dershowitz e Yuri Gurevich. “When are two
algorithms the same?”  Em: Bulletin of Symbolic Logic 15.2 (2009),
pp. 145–168.
--8<---------------cut here---------------end--------------->8---

I'll appreciate hearing what you guys have to say about any of this.

[toc] | [prev] | [next] | [standalone]

#164742 — Re: on legal definitions of a certain algorithm

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.

[toc] | [prev] | [next] | [standalone]

#164743 — Re: on legal definitions of a certain algorithm

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.

[toc] | [prev] | [next] | [standalone]

#164745 — Re: on legal definitions of a certain algorithm

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.

[toc] | [prev] | [next] | [standalone]

#164751 — Re: on legal definitions of a certain algorithm

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Meredith Montgomery <mmontgomery@levado.to> writes:
>>  while True:
>>    while True:
>>      i = i + 1
>>      if A[i] >= pivot:
>>        break
>
>   I'm not sure whether, in Python, this loop will ever exit!

It won't.  I messed up the indentation.  Here it is again.

--8<---------------cut here---------------start------------->8---
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]
--8<---------------cut here---------------end--------------->8---

>>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.
>
>   I wrote this quicksort that's not only functional, but also visual:

Beautiful!  But is it ``quicksort''?

>
>                                 .--------------------------------------------.
>                                 |    .---------------.                       |
>                                 |    |     .----.    |                       |
>                                 |    |   ->|    |    |                       |
>        .-------.                |    |     | <= | -> |                       |
> [] --->| qsort |---> []         |    | x ->|    |    |                       |
>        '-------'                |    |     '----'    |                       |
>                                 |    '---------------'                       |
>                                 |            |                               |
>                                 |            v                    .---.      |
>                                 |        .------.   .-------.     |   |      |
> .---------------.               |  xs -->| grep | ->| qsort | --->|   |      |
> |      .---.    |               |        '------'   '-------'     | j |      |
> | x -->|   |    |   .-------.   |        .------.                 | o |      |
> |      | : | -> |-->| qsort | ->|  x --->| list | --------------->| i | -->  |
> | xs ->|   |    |   '-------'   |        '------'                 | n |      |
> |      '___'    |               |        .------.   .-------.     |   |      |
> '---------------'               |  xs -->| grep | ->| qsort | --->|   |      |
>                                 |        '------'   '-------'     |   |      |
>                                 |            ^                    '---'      |
>                                 |            |                               |
>                                 |    .---------------.                       |
>                                 |    |     .----.    |                       |
>                                 |    | x ->|    |    |                       |
>                                 |    |     | <  | -> |                       |
>                                 |    |   ->|    |    |                       |
>                                 |    |     '----'    |                       |
>                                 |    '---------------'                       |
>                                 '--------------------------------------------'

[toc] | [prev] | [next] | [standalone]

#164746 — Re: on legal definitions of a certain algorithm

Meredith Montgomery <mmontgomery@levado.to> writes:

> [...]
>
> I'll appreciate hearing what you guys have to say about any of
> this.

If you don't mind a suggestion, I think it would be helpful if
you would put less effort into acquiring knowledge, and more into
gaining understanding.

[toc] | [prev] | [next] | [standalone]

#164556 — Re: **********@b*****.uk

On Sunday, 23 January 2022 at 15:48:47 UTC, Kaz Kylheku wrote:
>
> Your teacher is an ignoramus, or else you are trolling. 
> 
That claim is commonly made, usually be people who don't
teach. It's necessary to simplify in the early stages of teaching
material. It's seldom the case that the teacher doesn't know that
what he is saying is technically wrong.

[toc] | [prev] | [next] | [standalone]

#164557 — This newsgroup (Was: for some totally inexplicable reason, **********@b*****.uk)

In article <cc61e709-6a41-40d6-8d40-cd128304d70dn@googlegroups.com>,
Malcolm McLean  <malcolm.arthur.mclean@gmail.com> wrote:
>On Sunday, 23 January 2022 at 15:48:47 UTC, Kaz Kylheku wrote:
>>
>> Your teacher is an ignoramus, or else you are trolling. 
>> 
>That claim is commonly made, usually be people who don't
>teach. It's necessary to simplify in the early stages of teaching
>material. It's seldom the case that the teacher doesn't know that
>what he is saying is technically wrong.

That sort of problem - the inability to grasp and practice "lies for
children" - is endemic on this newsgroup.

-- 
Pensacola - the thinking man's drink.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web