Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #398025

Re: sorting Was: Isn't that beauty ? (no it's not)

Show key headers only | View raw

cross@spitfire.i.gajendra.net (Dan Cross) writes:

> In article <86fr4i3ben.fsf@linuxsc.com>,
> Tim Rentsch  <tr.17687@z991.linuxsc.com> wrote:
>
>> cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>
>>> In article <86fr508dwq.fsf@linuxsc.com>,
>>> Tim Rentsch  <tr.17687@z991.linuxsc.com> wrote:

[..trimming some earlier portions..]

>>>> [...]  BigO was already part of the discussion
>>>> when I joined in.  Also, it is customary in discussion of sorting
>>>> algorithms to use the metric of number of comparisons done, without
>>>> regard to the size of the variables needed to hold the indices of
>>>> the records being sorted.
>>>
>>> Hmm, this response echoes almost exactly what I wrote in
>>> <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in
>>> response to Waldek.  Did you see it?
>>
>> Probably, but I don't remember it specifically.
>
> Very well.
>
>>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP.
>>>
>>> As for TAOCP, as much as I respect and admire Knuth, I don't
>>> think "The Art of Computer Programming" is a good reference for
>>> working programmers.  At 391 pages long, Chapter Five occupies
>>> more than half of an ~750 page book, the examples are all in
>>> assembly language for his notional MIX computer, and the
>>> analysis he presents presumes a mathematics background that,
>>> frankly, most programmers neither have nor need.
>>
>> I am not recommending TAOCP as a textbook.
>
> No, but you are referring to it and suggesting that someone else
> do the same;  ie, using it as a reference and giving it to
> another as a reference.

I said this:

>>>> Also, it is customary in discussion of sorting algorithms to use
>>>> the metric of number of comparisons done, without regard to the
>>>> size of the variables needed to hold the indices of the records
>>>> being sorted.

I then said this:

>>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP.

This chapter in TAOCP discusses sorting algorithms.  Most of the
discussion uses the number of comparisons needed, as a function of
the number of records to be sorted (and only that) in characterizing
the different algorithms.

>> It's a well-known work
>> and respected for its theoretical treatments.  Also it happens to be
>> what I consulted before posting, mainly because it was handy.
>
> What part?  As I mentioned, "Chapter 5" of TAOCP is nearly 400
> pages long, and touches on a great many things.  It's not at all
> clear what precisely, from that book-length chapter, you may be
> referring to.

Most of the discussion in that chapter.

> Further, "See Knuth chapter 5" is an imperative statement, not a
> statement of fact about something you had done.
>
> My point is that, if your goal is to a establish shared working
> vocabulary with Waldek, such a directive is, unfortunately, not
> likely to be particularly useful towards that goal.

My goal was only to support my statement "it is customary in
discussion of sorting algorithms to use the metric of number of
comparisons done [...]".  No goal other than that.

>>> "See chapter 5" is thus not useful as a reference, and rather
>>> comes across as an admonishment.
>>
>> No admonishment was intented.  I mentioned it only as a supporting
>> work for my previous statement.
>
> My point is that the statement is too vague.  A more useful
> citation would be to a section, or perhaps a page number,
> edition, and printing, or perhaps a direct quotation.

I'm sorry you thought the statement was too vague.  I thought it
was clear enough when I wrote it.

> Absent a more refined citation, the reference to Knuth comes
> across as more of an appeal to authority than something that is
> actually meant to illuminate the discussion.

The reference to Knuth was only to support my earlier statement.
I had thought that was evident.

> I trust you that that was Not your intent, however.
>
> I do think this is actually useful, even in the context of
> comp.lang.c; a lot of people posting here seem to have forgotten
> many of the finer points of analyzing the characteristics of the
> code that is frequently under discussion, and understanding how
> to apply such to C code is an important skill.

In any discussion it's important to keep in mind which details are
essential to the discussion and which ones are better left out.  It
was my judgment that in the context of the post(s) I was responding
to that the number of comparisons, as a function of the number of
records to be sorted, was a key part of the discussion, but that
more detailed analysis was unnecessary.  Other people are free to
have their own views on that question.  However, for what I was
trying to get across, I still think the level of detail I settled
on was an appropriate choice for what I was hoping to convey.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-25 15:47 -0700
  Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-27 02:04 +0000
    Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-26 22:27 -0700
      Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-27 14:41 +0000

csiph-web