Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397520
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Date | 2026-04-13 20:44 +0000 |
| Organization | PANIX Public Access Internet and UNIX, NYC |
| Message-ID | <10rjkin$otp$1@reader1.panix.com> (permalink) |
| References | <10otm7r$1ntrg$1@raubtier-asyl.eternal-september.org> <863416xid5.fsf@linuxsc.com> <10r9d06$32585$1@paganini.bofh.team> <86fr508dwq.fsf@linuxsc.com> |
In article <86fr508dwq.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >antispam@fricas.org (Waldek Hebisch) writes: >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> antispam@fricas.org (Waldek Hebisch) writes: >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>> Michael S <already5chosen@yahoo.com> writes: >>>>>> On Mon, 06 Apr 2026 15:13:32 -0700 >>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>>> >>>>>>> Obviously what words (or lines) appear can affect the character >>>>>>> counts, but that still doesn't change BigO. By the way you don't >>>>>>> say whether you are sorting words or lines. >>>>>> >>>>>> This sub-thread is about sorting lines with average length of few >>>>>> dozens characters, i.e. many times longer than log2(N). That was >>>>>> stated at one of earlier posts. >>>>> >>>>> That has nothing to do with BigO, which is about asymptotic >>>>> behavior as N goes to infinity. >>>> >>>> Honest Big(O) varies length of the key with N. In practical range >>>> key length may be constant, but fixing length gives unrealistic >>>> problem for Big(O) analysis: without varying key length there are >>>> finitely many keys and sorting is equivalent to counting how many >>>> times each key appears in the input. >>> >>> There's an important clarification to make here. There are two >>> independent parameters: N, the number of records to be sorted (a >>> record being a character string that is either a word or a line), >>> and the (maximum) length of any record, which in the discussion is >>> bounded above by a constant. >> >> 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? >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. "See chapter 5" is thus not useful as a reference, and rather comes across as an admonishment. A much more useful treatment is Cormen, Leiserson, Rivest, and Stein's, "Introduction to Algorithms." The treatment is much more accessible than TAOCP, while still rigorous. Disclaimer: I once served as a industry mentor for students taking one of Leiserson's classes, though I haven't worked with him closely. CLRS suggests that Aho, Hopcroft, and Ullman advocated for asymptotic analysis of algorithms in, "The Design and Analysis of Computer Algorithms". Again, it's a wonderful book, but I would argue it's more theoretical than most programmers would find comfortable. Disclaimer: Aho taught me compilers. Personally, I like Skiena's, "Algorithm Design Manual" and think that its treatment is among the best I've seen when it comes to threading the needle between rigorous attention to detail and accessibility, though one needs more mathematics to negotiate it than e.g., CLRS. - Dan C.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:41 -0400
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 00:29 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 05:38 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 11:47 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 13:08 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 12:37 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 02:40 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-18 11:21 +0200
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 10:49 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 15:10 +0000
Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-18 21:20 +0000
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 23:13 +0000
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 13:23 -0700
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-18 11:20 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 21:57 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 22:01 +0100
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 10:43 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 12:23 +0200
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 15:22 +0100
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-19 15:07 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:16 +0100
Re: Isn't that beauty ? (no it's not) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-03-20 02:14 -0700
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:38 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-20 13:06 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 13:27 +0100
Re: Isn't that beauty ? (no it's not) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-03-20 13:22 -0700
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-21 02:25 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-19 16:13 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:41 +0200
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:01 +0100
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 08:35 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:47 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:42 +0200
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:39 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 08:33 +0200
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-20 17:10 -0400
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-21 02:53 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-20 22:35 -0400
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-21 14:42 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:57 +0100
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 12:32 -0700
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:50 +0100
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-21 15:39 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-22 15:48 -0400
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-22 23:04 +0100
Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 13:28 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 03:45 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 11:19 +0200
Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 10:49 +0100
Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 14:09 +0000
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 14:49 +0000
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:09 +0200
sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:29 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 18:33 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 21:40 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 23:53 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-20 00:15 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 05:05 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 12:58 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:53 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 13:13 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 13:26 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 15:08 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-20 13:43 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 15:51 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 14:47 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 02:03 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:03 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:13 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 02:22 +0300
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 21:00 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 09:37 +0300
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 21:54 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-09 16:06 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 09:04 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-11 19:55 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-04-07 14:46 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 20:04 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-09 21:15 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-10 01:31 +0300
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 06:17 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 21:32 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-12 04:59 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-26 07:29 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-04-09 23:33 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-10 11:35 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 07:13 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-13 20:44 +0000
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) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:01 +0200
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 13:48 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 01:58 +0300
Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-04-07 01:02 +0100
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 08:01 -0700
Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 23:21 +0000
Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 18:37 -0700
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:33 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:24 +0200
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 05:06 +0100
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 09:30 +0200
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 02:12 -0700
Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 14:00 +0300
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 10:23 -0700
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-04-07 16:39 -0400
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 11:16 -0700
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-25 00:45 +0000
csiph-web