Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.lang.c > #398023

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

Show all headers | View raw

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:
>>> antispam@fricas.org (Waldek Hebisch) writes:
>>>> [snip]
>>>> There is one choice, made often to simplify problem.  But there
>>>> is quite universal choice:  N is total size of input data.
>>>
>>> No, N is usually the number of records to be sorted, not the size of
>>> the input.  Also, in the discussion I was responding to, there were
>>> clearly two distinct axes relevant to the discussion.
>>>
>>>>> What is being asked about is the behavior as a function of N as N
>>>>> increases without bound.  Of course, theoretically, as the number of
>>>>> records increases without bound, eventually the character strings
>>>>> being sorted will have to have duplicates.  But long before that
>>>>> happens the index variable N will run out of bits.  This property is
>>>>> well understood in theoretical computer science, not just in terms
>>>>> of how much time is used but how much storage is needed.  In theory
>>>>> log N bits are needed just to hold the index pointers.  It is
>>>>> customary though, outside of purely theoretical discussions, to
>>>>> ignore that and treat the size of an index or pointer variable as
>>>>> constant.  In purely theoretical terms no sorting algorithm is
>>>>> O(N*log(N)), because just incrementing a pointer takes more than
>>>>> O(1) operations.  Surely the discussions in Knuth's books take such
>>>>> things into consideration.  On the practical side, which almost
>>>>> always covers discussions that take place in usenet newsgroups,
>>>>> these minor theoretical issues are ignored.  Any actul computer in
>>>>> the physical universe will never have occasion to process more than
>>>>> 2**512 records, due to the limitation of the number of elementary
>>>>> particles in the universe, so a 512-bit address (or index value)
>>>>> always suffices.
>>>>>
>>>>> So yes, in theory, the considerations around processing an enormous
>>>>> number of values are relevant.  In the practical context of the
>>>>> discussion underway here, they aren't.
>>>>
>>>> It was you who insisted on asymptitic complexity, rejecting
>>>> practical amendments...
>>>
>>> This statement isn't right.  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.

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

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.

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

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.

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. 

	- Dan C.

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