Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #396916 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2026-03-12 07:24 +0100 |
| Last post | 2026-03-27 17:03 +0000 |
| Articles | 20 on this page of 231 — 18 participants |
Back to article view | Back to comp.lang.c
Isn't that beauty ? Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 07:24 +0100
Re: Isn't that beauty ? Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 07:26 +0100
Re: Isn't that beauty ? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-12 09:32 +0100
Re: Isn't that beauty ? Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 11:36 +0100
Re: Isn't that beauty ? Janis Papanagnou <janis_papanagnou@hotmail.com> - 2026-03-12 20:15 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-12 10:00 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 15:03 +0100
Re: Isn't that beauty ? (no it's not) tTh <tth@none.invalid> - 2026-03-12 15:27 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 15:34 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 15:13 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-12 10:43 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 16:10 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-12 11:22 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 16:25 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 16:25 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 16:48 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou@hotmail.com> - 2026-03-12 20:25 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 00:57 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou@hotmail.com> - 2026-03-13 02:19 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 06:14 +0100
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 01:48 -0700
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 09:49 +0100
[OT] AI - questions and answers (was Re: Isn't that beauty ? (no it's not)) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-13 10:27 +0100
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 11:59 -0700
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-12 21:22 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 06:15 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 06:48 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-14 03:29 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-12 16:44 +0100
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-12 17:32 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 00:56 +0100
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 11:54 -0700
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 01:14 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-12 16:18 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 01:06 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 01:27 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 16:11 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 06:01 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-14 01:49 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 07:23 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-14 02:58 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 07:52 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 07:53 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-14 03:05 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 08:10 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-14 03:17 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 08:59 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 09:12 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-14 12:15 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 14:00 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 16:43 -0400
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-16 20:57 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:07 -0400
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-17 00:49 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 05:21 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 12:40 -0400
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 17:06 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 15:46 -0400
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 22:14 +0000
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-19 22:39 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 16:14 -0400
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-19 22:42 +0000
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-17 14:46 +0000
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 22:26 +0000
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-16 22:35 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:09 -0400
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 23:17 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:21 -0400
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 23:34 +0000
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 00:09 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 21:45 -0400
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 10:42 +0000
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 13:04 +0100
Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 12:17 +0000
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 12:31 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 21:27 -0400
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-16 22:26 +0000
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) 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
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
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-17 06:25 +0100
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-20 01:33 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-20 07:42 +0100
Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-20 12:16 +0000
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-14 16:22 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 18:04 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-14 17:39 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 19:25 +0100
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-13 00:54 +0000
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 00:31 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 06:24 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 01:40 -0400
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 01:34 -0400
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-13 14:38 +0000
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-13 15:31 +0000
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-15 13:15 -0700
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-16 15:18 +0000
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-23 21:23 -0700
Re: Isn't that beauty ? (no it's not) James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-03-13 18:47 -0400
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-15 14:38 -0700
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 07:24 +0100
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 01:51 -0700
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 09:54 +0100
Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-13 10:29 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 10:33 +0100
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 11:57 -0700
Re: Isn't that beauty ? (no it's not) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-03-13 11:58 -0700
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-13 14:29 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 08:08 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 04:19 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 09:53 +0100
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 09:56 +0100
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-13 05:10 -0400
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 10:14 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-13 17:32 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-13 18:44 +0100
Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-13 19:36 +0000
Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-14 06:03 +0100
Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-12 16:56 +0000
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-20 23:07 -0700
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-22 16:55 -0400
Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-26 20:08 -0700
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-27 00:35 -0400
Re: Isn't that beauty ? (no it's not) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-03-26 21:53 -0700
Re: Isn't that beauty ? (no it's not) gazelle@shell.xmission.com (Kenny McCormack) - 2026-03-27 17:03 +0000
Page 8 of 12 — ← Prev page 1 … 6 7 [8] 9 10 … 12 Next page →
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2026-03-20 13:43 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10pjiuk$1jpmn$1@dont-email.me> |
| In reply to | #397118 |
On 20/03/2026 13:08, Michael S wrote: > On Fri, 20 Mar 2026 13:26:34 +0100 > David Brown <david.brown@hesbynett.no> wrote: > >> On 20/03/2026 13:13, Janis Papanagnou wrote: >>> On 2026-03-20 11:58, Michael S wrote: >>>> [...] >>>> BTW, quicksort is O(N*logN) only as long as comparison is O(1). >>>> Which does not hold in the general case of lexicographic sort. >>> >>> You have to differentiate the complexity of an _algorithm_ here; >>> we talk about how many comparisons and how many data swaps are >>> necessary. >>> >>> If your _comparisons_ are costly, or your _data swaps_ are costly, >>> we don't blame the algorithm. If you happen to have a comparison >>> function of some O(X) the _sorting algorithm_ is still of its own >>> inherent algorithmic complexity. If you happen to swap BLOB data >>> by copying every byte (instead of sorting an index, for example) >>> you also cannot blame the sorting algorithm, its complexity still >>> holds. >>> >>> If it were different any complexity measure for algorithms would >>> be meaningless. >>> >> >> That's all true. >> > > No, it is not. That's all nonsense that demonstrates a shallow thinking. > Comparison method one uses in lexicographic sort is very much > variable part of algorithm rather than something fixed. > Many good methods start sorting by using just few (sometimes one) > leading characters and only in later passes that typically operate on > much much shorter sections, they use full string comparison. I just tried something like that with bubble-sort: I split the data into 26 arrays each only containing strings that start with 'a', 'b', 'c' and so on. The arrays were sorted separately then concatenated (so no longer in-place unless I take the extra step of overwriting the original). Sorting 20K random strings reduced from 25 seconds to 0.8 seconds (interpreted code). Of course, being random strings (and also all lower case), there was a near-perfect distribution of strings starting with each letter! It also requires extra storage and copying.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-03-20 15:51 +0200 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260320155158.00005f05@yahoo.com> |
| In reply to | #397119 |
On Fri, 20 Mar 2026 13:43:50 +0000 Bart <bc@freeuk.com> wrote: > On 20/03/2026 13:08, Michael S wrote: > > On Fri, 20 Mar 2026 13:26:34 +0100 > > David Brown <david.brown@hesbynett.no> wrote: > > > >> On 20/03/2026 13:13, Janis Papanagnou wrote: > >>> On 2026-03-20 11:58, Michael S wrote: > >>>> [...] > >>>> BTW, quicksort is O(N*logN) only as long as comparison is O(1). > >>>> Which does not hold in the general case of lexicographic sort. > >>> > >>> You have to differentiate the complexity of an _algorithm_ here; > >>> we talk about how many comparisons and how many data swaps are > >>> necessary. > >>> > >>> If your _comparisons_ are costly, or your _data swaps_ are costly, > >>> we don't blame the algorithm. If you happen to have a comparison > >>> function of some O(X) the _sorting algorithm_ is still of its own > >>> inherent algorithmic complexity. If you happen to swap BLOB data > >>> by copying every byte (instead of sorting an index, for example) > >>> you also cannot blame the sorting algorithm, its complexity still > >>> holds. > >>> > >>> If it were different any complexity measure for algorithms would > >>> be meaningless. > >>> > >> > >> That's all true. > >> > > > > No, it is not. That's all nonsense that demonstrates a shallow > > thinking. Comparison method one uses in lexicographic sort is very > > much variable part of algorithm rather than something fixed. > > Many good methods start sorting by using just few (sometimes one) > > leading characters and only in later passes that typically operate > > on much much shorter sections, they use full string comparison. > > I just tried something like that with bubble-sort: I split the data > into 26 arrays each only containing strings that start with 'a', 'b', > 'c' and so on. > > The arrays were sorted separately then concatenated (so no longer > in-place unless I take the extra step of overwriting the original). > > Sorting 20K random strings reduced from 25 seconds to 0.8 seconds > (interpreted code). > You wouldn't see anything near that speed up with O(N*logN) algorithm. > Of course, being random strings (and also all lower case), there was > a near-perfect distribution of strings starting with each letter! > On the other hand, being random string means that strcmp() is very close to O(1). So, may be, it illustrates related point, but it can not illustate my original point. > It also requires extra storage and copying. > You win some, you lose some. So it goes.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-03-20 14:47 +0100 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10pjj56$1k50i$1@dont-email.me> |
| In reply to | #397118 |
On 20/03/2026 14:08, Michael S wrote: > On Fri, 20 Mar 2026 13:26:34 +0100 > David Brown <david.brown@hesbynett.no> wrote: > >> On 20/03/2026 13:13, Janis Papanagnou wrote: >>> On 2026-03-20 11:58, Michael S wrote: >>>> [...] >>>> BTW, quicksort is O(N*logN) only as long as comparison is O(1). >>>> Which does not hold in the general case of lexicographic sort. >>> >>> You have to differentiate the complexity of an _algorithm_ here; >>> we talk about how many comparisons and how many data swaps are >>> necessary. >>> >>> If your _comparisons_ are costly, or your _data swaps_ are costly, >>> we don't blame the algorithm. If you happen to have a comparison >>> function of some O(X) the _sorting algorithm_ is still of its own >>> inherent algorithmic complexity. If you happen to swap BLOB data >>> by copying every byte (instead of sorting an index, for example) >>> you also cannot blame the sorting algorithm, its complexity still >>> holds. >>> >>> If it were different any complexity measure for algorithms would >>> be meaningless. >>> >> >> That's all true. >> > > No, it is not. That's all nonsense that demonstrates a shallow thinking. > Comparison method one uses in lexicographic sort is very much > variable part of algorithm rather than something fixed. > Many good methods start sorting by using just few (sometimes one) > leading characters and only in later passes that typically operate on > much much shorter sections, they use full string comparison. > One example where doing it smart is particularly beneficial is a sort > at core of Burrows-Wheeler Transform. Yes, I realise that various kinds of radix or bucket sorts are often good for large data sets, either in whole or as the first steps. But I am not clear about how it contradicts what Janis has been saying - I feel the two of you are talking somewhat past each other. The cost of doing a comparison does not affect the complexity of an algorithm - but it can certainly affect the best choice of algorithm for the task in hand. > >> If you have a situation where swaps are particularly costly, or >> comparisons are particularly costly, or other factors (such as memory >> usage) are particularly costly, then you might have to be more >> nuanced in the complexity measurements you use when comparing >> algorithms. You might find that an algorithm that is O(n²) in >> comparisons but O(n) in swaps is better for that purpose than one >> that is O(n.log n) in both. >> >> And don't forget that the constant factors in the O can be relevant. >> There's a known algorithm for multiplication of big numbers that is >> O(n.log n), which is (probably) the optimal order of complexity for >> the task. But the constant factors mean it is only better than other >> algorithms once you are using truly absurdly big numbers (so that you >> are saving a few minutes in your million-year calculations). >> >> Sometimes a single O number is not nearly enough to tell you what you >> need to know in comparisons between algorithms. >> >> > >
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-03-22 02:03 +0200 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260322020323.00006a16@yahoo.com> |
| In reply to | #397120 |
On Fri, 20 Mar 2026 14:47:18 +0100 David Brown <david.brown@hesbynett.no> wrote: > On 20/03/2026 14:08, Michael S wrote: > > On Fri, 20 Mar 2026 13:26:34 +0100 > > David Brown <david.brown@hesbynett.no> wrote: > > > >> On 20/03/2026 13:13, Janis Papanagnou wrote: > >>> On 2026-03-20 11:58, Michael S wrote: > >>>> [...] > >>>> BTW, quicksort is O(N*logN) only as long as comparison is O(1). > >>>> Which does not hold in the general case of lexicographic sort. > >>> > >>> You have to differentiate the complexity of an _algorithm_ here; > >>> we talk about how many comparisons and how many data swaps are > >>> necessary. > >>> > >>> If your _comparisons_ are costly, or your _data swaps_ are costly, > >>> we don't blame the algorithm. If you happen to have a comparison > >>> function of some O(X) the _sorting algorithm_ is still of its own > >>> inherent algorithmic complexity. If you happen to swap BLOB data > >>> by copying every byte (instead of sorting an index, for example) > >>> you also cannot blame the sorting algorithm, its complexity still > >>> holds. > >>> > >>> If it were different any complexity measure for algorithms would > >>> be meaningless. > >>> > >> > >> That's all true. > >> > > > > No, it is not. That's all nonsense that demonstrates a shallow > > thinking. Comparison method one uses in lexicographic sort is very > > much variable part of algorithm rather than something fixed. > > Many good methods start sorting by using just few (sometimes one) > > leading characters and only in later passes that typically operate > > on much much shorter sections, they use full string comparison. > > One example where doing it smart is particularly beneficial is a > > sort at core of Burrows-Wheeler Transform. > > Yes, I realise that various kinds of radix or bucket sorts are often > good for large data sets, either in whole or as the first steps. But > I am not clear about how it contradicts what Janis has been saying - > I feel the two of you are talking somewhat past each other. Read the thread. We were talking with Bart and understanding each other well enough. Then came Janis with ignorant statement that in effect was saying that plain quicksort algorithm with strcmp() as comparison routine is optimal or close to optimal for lexicographic sorting similar to one done by Linux or Windows sort commands applied to text files with 20K to 1M lines of average length of few dozens characters. > The cost > of doing a comparison does not affect the complexity of an algorithm > - but it can certainly affect the best choice of algorithm for the > task in hand. > In case of lexicographic sort comparison most certainly affects BigO. BigO is about counting elementary operations or, at least, about counting non-elementary operations that have complexity independent of N. In out specific case (described in the previous paragraph) an average number of elementary comparisons within strcmp() does depend on N. One can expect that it grows with N, because for longer N quicksort spends relatively more time comparing strings with longer and longer common prefixes. I did a couple of experiments. Here is a number of character comparisons during sorting by quicksort with strcmp-alike comparison as a function number of sorted strings. Inputs used for experiments were first N lines of two long books (those that I suggested to Bart in other post in this thread). Book 1: 1000 40367 2000 93404 3000 156995 4000 238062 5000 322275 6000 401332 7000 483294 8000 588128 9000 707559 10000 811159 11000 969934 12000 1061037 13000 1172776 14000 1327489 15000 1456356 16000 1565355 17000 1691351 18000 1811836 19000 1971700 20000 2101477 21000 2237132 22000 2348410 23000 2492149 24000 2618858 25000 2726828 26000 2881609 27000 3017903 28000 3183088 29000 3320716 30000 3523695 31000 3719782 32000 3852290 33000 4007476 34000 4149704 35000 4228143 36000 4399583 37000 4581223 38000 4761085 39000 4919182 40000 5110223 41000 5463271 42000 5605860 43000 5830282 44000 6096857 45000 6464758 46000 6860786 47000 7101972 48000 7434769 49000 7736464 50000 8028681 51000 8334358 52000 8560822 53000 8814096 54000 8986343 55000 9162604 56000 9358948 57000 9468853 58000 9638512 59000 9863370 60000 10000734 61000 10242187 62000 10500148 63000 10654166 64000 10882232 65000 11187624 66000 11290778 67000 11481047 68000 11664433 69000 11858529 70000 12059970 71000 12173240 72000 12232160 73000 12418818 74000 12577954 75000 12786122 76000 12939916 77000 13083515 78000 13275432 79000 13616563 80000 13797048 81000 14137362 82000 14388124 83000 14667272 84000 14914600 85000 15174195 86000 15227048 87000 15414838 88000 15526278 89000 15670034 90000 15966396 91000 16120859 92000 16267285 93000 16402168 94000 16718506 95000 16968960 96000 17169618 97000 17362159 98000 17486179 99000 17944209 100000 18085095 101000 18455071 102000 18733130 102100 18769521 Book 2: 1000 104846 2000 243080 3000 399564 4000 661436 5000 855870 6000 1017042 7000 1205936 8000 1341884 9000 1511727 10000 1681973 11000 1820114 12000 1978196 13000 2081813 14000 2162091 15000 2280537 16000 2375272 17000 2500672 18000 2617364 19000 2787782 20000 2960678 21000 3149483 22000 3286894 23000 3481047 24000 3638352 25000 3842186 26000 4001105 27000 4083466 28000 4239273 29000 4399250 30000 4505316 30384 4598719 It is easy to see that at the beginning # of comparisons grows faster than N*log(N). For the 1st book the trend continues throughout all chart. For the 2nd book it does not. I'd guess that the reasons behind it is that the 1st book is relatively homogeneous, while the 2nd book consists of rather distinct parts, likely with different characteristics of beginnings of lines. At parts the 2nd book is full of periods, of rhythmical prose close to poetry and at other parts it is not. I didn't have time to dig deeper.
[toc] | [prev] | [next] | [standalone]
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Date | 2026-03-22 04:03 +0100 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10pnm6s$2ut13$1@dont-email.me> |
| In reply to | #397131 |
On 2026-03-22 01:03, Michael S wrote: > On Fri, 20 Mar 2026 14:47:18 +0100 > David Brown <david.brown@hesbynett.no> wrote: >> On 20/03/2026 14:08, Michael S wrote: >>> On Fri, 20 Mar 2026 13:26:34 +0100 >>> David Brown <david.brown@hesbynett.no> wrote: >>>> On 20/03/2026 13:13, Janis Papanagnou wrote: >>>>> On 2026-03-20 11:58, Michael S wrote: >>>>>> [...] >>>>>> BTW, quicksort is O(N*logN) only as long as comparison is O(1). >>>>>> Which does not hold in the general case of lexicographic sort. >>>>> >>>>> You have to differentiate the complexity of an _algorithm_ here; >>>>> we talk about how many comparisons and how many data swaps are >>>>> necessary. >>>>> >>>>> If your _comparisons_ are costly, or your _data swaps_ are costly, >>>>> we don't blame the algorithm. If you happen to have a comparison >>>>> function of some O(X) the _sorting algorithm_ is still of its own >>>>> inherent algorithmic complexity. If you happen to swap BLOB data >>>>> by copying every byte (instead of sorting an index, for example) >>>>> you also cannot blame the sorting algorithm, its complexity still >>>>> holds. >>>>> >>>>> If it were different any complexity measure for algorithms would >>>>> be meaningless. >>>>> >>>> >>>> That's all true. >>>> >>> >>> No, it is not. That's all nonsense that demonstrates a shallow >>> thinking. Comparison method one uses in lexicographic sort is very >>> much variable part of algorithm rather than something fixed. >>> Many good methods start sorting by using just few (sometimes one) >>> leading characters and only in later passes that typically operate >>> on much much shorter sections, they use full string comparison. >>> One example where doing it smart is particularly beneficial is a >>> sort at core of Burrows-Wheeler Transform. >> >> Yes, I realise that various kinds of radix or bucket sorts are often >> good for large data sets, either in whole or as the first steps. But >> I am not clear about how it contradicts what Janis has been saying - >> I feel the two of you are talking somewhat past each other. > > Read the thread. We were talking with Bart and understanding each other > well enough. Then came Janis with ignorant statement that in effect was > saying that plain quicksort algorithm with strcmp() as comparison > routine is optimal or close to optimal for lexicographic sorting > similar to one done by Linux or Windows sort commands applied to text > files with 20K to 1M lines of average length of few dozens characters. What I said were various things; correcting mainly misinformation (or inaccuracies) you spread! - Basically that the O-complexity measures of sorting algorithms do not include the effort you spend in the comparison function or in the data-move function. If they did they would be *arbitrary* and no _reliable quality measure_ of algorithms! (Then you could compare e.g. climatic state of two country entries by doing the complex hydrodynamic calculations and the whole sorting function would become of combinatorial complexity. This is an extreme example but makes your wrong thinking obvious. Less extreme examples are the already mentioned physical move-operations of BLOBs, instead of working with indexes/references/pointers.) The main point with Bart was his "reasoning" for his use of Bubblesort which was just ridiculous. > >> The cost >> of doing a comparison does not affect the complexity of an algorithm >> - but it can certainly affect the best choice of algorithm for the >> task in hand. Yes, indeed. - The program designer has still the responsibility to choose, besides the appropriate sorting algorithms, also the way how to implement the whole function efficiently. Janis > [...]
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-06 15:13 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <864ilnzqib.fsf@linuxsc.com> |
| In reply to | #397131 |
Michael S <already5chosen@yahoo.com> writes: > On Fri, 20 Mar 2026 14:47:18 +0100 > David Brown <david.brown@hesbynett.no> wrote: > >> The cost of doing a comparison does not affect the complexity of >> an algorithm - but it can certainly affect the best choice of >> algorithm for the task in hand. > > In case of lexicographic sort comparison most certainly affects > BigO. BigO is about counting elementary operations or, at least, > about counting non-elementary operations that have complexity > independent of N. In out specific case (described in the previous > paragraph) an average number of elementary comparisons within > strcmp() does depend on N. One can expect that it grows with N, > because for longer N quicksort spends relatively more time > comparing strings with longer and longer common prefixes. This reasoning isn't right. The reason it isn't is that, even as more words are sorted, the words don't get longer. Average match length doesn't matter. All words in the two files mentioned are, as best I can determine, not longer than 40 characters. Because the length is bounded, so is the time needed to do a strcmp() call. In other words the comparison operation is O(1). Using strcmp() can change the constant factor, but it doesn't change BigO. > I did a couple of experiments. > Here is a number of character comparisons during sorting by > quicksort with strcmp-alike comparison as a function number of > sorted strings. Inputs used for experiments were first N lines of > two long books (those that I suggested to Bart in other post in > this thread). > > > Book 1: > 1000 40367 > 2000 93404 > 3000 156995 > 4000 238062 > 5000 322275 > 6000 401332 > 7000 483294 > 8000 588128 > 9000 707559 > 10000 811159 > 11000 969934 > 12000 1061037 > 13000 1172776 > 14000 1327489 > 15000 1456356 > 16000 1565355 > 17000 1691351 > 18000 1811836 > 19000 1971700 > 20000 2101477 > 21000 2237132 > 22000 2348410 > 23000 2492149 > 24000 2618858 > 25000 2726828 > 26000 2881609 > 27000 3017903 > 28000 3183088 > 29000 3320716 > 30000 3523695 > 31000 3719782 > 32000 3852290 > 33000 4007476 > 34000 4149704 > 35000 4228143 > 36000 4399583 > 37000 4581223 > 38000 4761085 > 39000 4919182 > 40000 5110223 > 41000 5463271 > 42000 5605860 > 43000 5830282 > 44000 6096857 > 45000 6464758 > 46000 6860786 > 47000 7101972 > 48000 7434769 > 49000 7736464 > 50000 8028681 > 51000 8334358 > 52000 8560822 > 53000 8814096 > 54000 8986343 > 55000 9162604 > 56000 9358948 > 57000 9468853 > 58000 9638512 > 59000 9863370 > 60000 10000734 > 61000 10242187 > 62000 10500148 > 63000 10654166 > 64000 10882232 > 65000 11187624 > 66000 11290778 > 67000 11481047 > 68000 11664433 > 69000 11858529 > 70000 12059970 > 71000 12173240 > 72000 12232160 > 73000 12418818 > 74000 12577954 > 75000 12786122 > 76000 12939916 > 77000 13083515 > 78000 13275432 > 79000 13616563 > 80000 13797048 > 81000 14137362 > 82000 14388124 > 83000 14667272 > 84000 14914600 > 85000 15174195 > 86000 15227048 > 87000 15414838 > 88000 15526278 > 89000 15670034 > 90000 15966396 > 91000 16120859 > 92000 16267285 > 93000 16402168 > 94000 16718506 > 95000 16968960 > 96000 17169618 > 97000 17362159 > 98000 17486179 > 99000 17944209 > 100000 18085095 > 101000 18455071 > 102000 18733130 > 102100 18769521 > > Book 2: > 1000 104846 > 2000 243080 > 3000 399564 > 4000 661436 > 5000 855870 > 6000 1017042 > 7000 1205936 > 8000 1341884 > 9000 1511727 > 10000 1681973 > 11000 1820114 > 12000 1978196 > 13000 2081813 > 14000 2162091 > 15000 2280537 > 16000 2375272 > 17000 2500672 > 18000 2617364 > 19000 2787782 > 20000 2960678 > 21000 3149483 > 22000 3286894 > 23000 3481047 > 24000 3638352 > 25000 3842186 > 26000 4001105 > 27000 4083466 > 28000 4239273 > 29000 4399250 > 30000 4505316 > 30384 4598719 > > It is easy to see that at the beginning # of comparisons grows faster > than N*log(N). For the 1st book the trend continues throughout all > chart. For the 2nd book it does not. 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. That choice has an effect, but as long as line lengths are bounded the strcmp() calls are still O(1). > I'd guess that the reasons behind it is that the 1st book is > relatively homogeneous, while the 2nd book consists of rather > distinct parts, likely with different characteristics of beginnings > of lines. At parts the 2nd book is full of periods, of rhythmical > prose close to poetry and at other parts it is not. I didn't have > time to dig deeper. A more careful experiment is needed.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-07 02:22 +0300 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260407022213.00001ae7@yahoo.com> |
| In reply to | #397394 |
On Mon, 06 Apr 2026 15:13:32 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Fri, 20 Mar 2026 14:47:18 +0100 > > David Brown <david.brown@hesbynett.no> wrote: > > > >> The cost of doing a comparison does not affect the complexity of > >> an algorithm - but it can certainly affect the best choice of > >> algorithm for the task in hand. > > > > In case of lexicographic sort comparison most certainly affects > > BigO. BigO is about counting elementary operations or, at least, > > about counting non-elementary operations that have complexity > > independent of N. In out specific case (described in the previous > > paragraph) an average number of elementary comparisons within > > strcmp() does depend on N. One can expect that it grows with N, > > because for longer N quicksort spends relatively more time > > comparing strings with longer and longer common prefixes. > > This reasoning isn't right. The reason it isn't is that, even as > more words are sorted, the words don't get longer. Average match > length doesn't matter. All words in the two files mentioned are, as > best I can determine, not longer than 40 characters. Because the > length is bounded, so is the time needed to do a strcmp() call. In > other words the comparison operation is O(1). Using strcmp() can > change the constant factor, but it doesn't change BigO. > > > I did a couple of experiments. > > Here is a number of character comparisons during sorting by > > quicksort with strcmp-alike comparison as a function number of > > sorted strings. Inputs used for experiments were first N lines of > > two long books (those that I suggested to Bart in other post in > > this thread). > > > > > > Book 1: > > 1000 40367 > > 2000 93404 > > 3000 156995 > > 4000 238062 > > 5000 322275 > > 6000 401332 > > 7000 483294 > > 8000 588128 > > 9000 707559 > > 10000 811159 > > 11000 969934 > > 12000 1061037 > > 13000 1172776 > > 14000 1327489 > > 15000 1456356 > > 16000 1565355 > > 17000 1691351 > > 18000 1811836 > > 19000 1971700 > > 20000 2101477 > > 21000 2237132 > > 22000 2348410 > > 23000 2492149 > > 24000 2618858 > > 25000 2726828 > > 26000 2881609 > > 27000 3017903 > > 28000 3183088 > > 29000 3320716 > > 30000 3523695 > > 31000 3719782 > > 32000 3852290 > > 33000 4007476 > > 34000 4149704 > > 35000 4228143 > > 36000 4399583 > > 37000 4581223 > > 38000 4761085 > > 39000 4919182 > > 40000 5110223 > > 41000 5463271 > > 42000 5605860 > > 43000 5830282 > > 44000 6096857 > > 45000 6464758 > > 46000 6860786 > > 47000 7101972 > > 48000 7434769 > > 49000 7736464 > > 50000 8028681 > > 51000 8334358 > > 52000 8560822 > > 53000 8814096 > > 54000 8986343 > > 55000 9162604 > > 56000 9358948 > > 57000 9468853 > > 58000 9638512 > > 59000 9863370 > > 60000 10000734 > > 61000 10242187 > > 62000 10500148 > > 63000 10654166 > > 64000 10882232 > > 65000 11187624 > > 66000 11290778 > > 67000 11481047 > > 68000 11664433 > > 69000 11858529 > > 70000 12059970 > > 71000 12173240 > > 72000 12232160 > > 73000 12418818 > > 74000 12577954 > > 75000 12786122 > > 76000 12939916 > > 77000 13083515 > > 78000 13275432 > > 79000 13616563 > > 80000 13797048 > > 81000 14137362 > > 82000 14388124 > > 83000 14667272 > > 84000 14914600 > > 85000 15174195 > > 86000 15227048 > > 87000 15414838 > > 88000 15526278 > > 89000 15670034 > > 90000 15966396 > > 91000 16120859 > > 92000 16267285 > > 93000 16402168 > > 94000 16718506 > > 95000 16968960 > > 96000 17169618 > > 97000 17362159 > > 98000 17486179 > > 99000 17944209 > > 100000 18085095 > > 101000 18455071 > > 102000 18733130 > > 102100 18769521 > > > > Book 2: > > 1000 104846 > > 2000 243080 > > 3000 399564 > > 4000 661436 > > 5000 855870 > > 6000 1017042 > > 7000 1205936 > > 8000 1341884 > > 9000 1511727 > > 10000 1681973 > > 11000 1820114 > > 12000 1978196 > > 13000 2081813 > > 14000 2162091 > > 15000 2280537 > > 16000 2375272 > > 17000 2500672 > > 18000 2617364 > > 19000 2787782 > > 20000 2960678 > > 21000 3149483 > > 22000 3286894 > > 23000 3481047 > > 24000 3638352 > > 25000 3842186 > > 26000 4001105 > > 27000 4083466 > > 28000 4239273 > > 29000 4399250 > > 30000 4505316 > > 30384 4598719 > > > > It is easy to see that at the beginning # of comparisons grows > > faster than N*log(N). For the 1st book the trend continues > > throughout all chart. For the 2nd book it does not. > > 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. If it was about sorting English words it would be completely different matter. Likely, dependency still exists for very short sorts, but likely disappers at few K words. > That choice has an > effect, but as long as line lengths are bounded the strcmp() calls > are still O(1). May be, for text, consistiong of many million of lines it would be the case. But the longest books ever written by human are much much shorter than that. > > > I'd guess that the reasons behind it is that the 1st book is > > relatively homogeneous, while the 2nd book consists of rather > > distinct parts, likely with different characteristics of beginnings > > of lines. At parts the 2nd book is full of periods, of rhythmical > > prose close to poetry and at other parts it is not. I didn't have > > time to dig deeper. > > A more careful experiment is needed. There aren't many books that are sufficiently long.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-06 21:00 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86mrzfxvv5.fsf@linuxsc.com> |
| In reply to | #397399 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-07 09:37 +0300 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260407093705.000025d1@yahoo.com> |
| In reply to | #397405 |
On Mon, 06 Apr 2026 21:00:46 -0700 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. So, how do you call part of the curve from 1e2 to 3e5 lines? MiddleO ?
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-07 21:54 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86y0iyvypl.fsf@linuxsc.com> |
| In reply to | #397407 |
Michael S <already5chosen@yahoo.com> writes: > On Mon, 06 Apr 2026 21:00:46 -0700 > 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. > > So, how do you call part of the curve from 1e2 to 3e5 lines? MiddleO ? Consider a thought experiment. We have a qsort-like sorting function, for the sake of discussion let's say it uses heapsort. It is widely understood that heapsort is an O(N*log(N)) algorithm (not counting the theoretical objections mentioned in Waldek Hebisch's post and my response to those comments). Now suppose we have two distinct invocations of said function. In both cases the arguments are length 1000 character strings, having only spaces and alphabetic characters, and no duplicates between the strings. In one call all the strings have distinct values in the first six characters, and in the other call the strings are all the same in the first 993 characters, differing only in the last six characters. The call to the sorting function points back to a function that uses strcmp() to do its comparisons. The heapsort algorithm is well-known to be N log N. All the strings in both sorts are exactly 1000 characters, so the strcmp() calls have a fixed maximum time cost. And yet one of these sorts runs almost 200 times as fast as the other. I think what you're seeing is a data dependency that is orthogonal to the time complexity of the algorithm. For example, the travelling salesman problem is widely known to be NP complete, and yet on some inputs a solution can be found very quickly. BigO is about worst case behavior, or sometimes average case behavior. Other kinds of behavior can depend dramatically on the nature of the inputs.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-09 16:06 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10r8iq8$m9$1@reader1.panix.com> |
| In reply to | #397420 |
In article <86y0iyvypl.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >Michael S <already5chosen@yahoo.com> writes: > >> On Mon, 06 Apr 2026 21:00:46 -0700 >> 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. >> >> So, how do you call part of the curve from 1e2 to 3e5 lines? MiddleO ? > >Consider a thought experiment. We have a qsort-like sorting function, >for the sake of discussion let's say it uses heapsort. It is widely >understood that heapsort is an O(N*log(N)) algorithm (not counting the >theoretical objections mentioned in Waldek Hebisch's post and my >response to those comments). > >Now suppose we have two distinct invocations of said function. In >both cases the arguments are length 1000 character strings, having >only spaces and alphabetic characters, and no duplicates between the >strings. In one call all the strings have distinct values in the >first six characters, and in the other call the strings are all the >same in the first 993 characters, differing only in the last six >characters. The call to the sorting function points back to a >function that uses strcmp() to do its comparisons. > >The heapsort algorithm is well-known to be N log N. All the strings >in both sorts are exactly 1000 characters, so the strcmp() calls have >a fixed maximum time cost. And yet one of these sorts runs almost 200 >times as fast as the other. > >I think what you're seeing is a data dependency that is orthogonal to >the time complexity of the algorithm. For example, the travelling >salesman problem is widely known to be NP complete, and yet on some >inputs a solution can be found very quickly. A useful thought experiment, but it is perhaps easier to explain that the asymptotic time complexity of a sorting algorithm, for example heapsort being O(n log n), is expressed in terms of the number of comparison operations required by the algorithm, independent of the complexity of those comparisons. Obviously, the real-world performance of such algorithms depends on the time required for the comparison, but analysis of algorithms themselves abstracts over that and considers it a constant. >BigO is about worst case >behavior, or sometimes average case behavior. Other kinds of behavior >can depend dramatically on the nature of the inputs. I disagree with this. The "Big-O" of an algorithm isn't about worst-case behavior, it's a notation for categorizing which term dominates in an expression describing the complexity of an algorithm, as the number of inputs to that algorithm grows. That is, it describe an aspect of rates of growth; "Big-O" in particular expresses an upper bound for such growth (so an O(n^2) algorithm is also O(n^3) and O(n^k) for k in 2..inf). Perhaps you meant "upper bound" instead of "worst case", but I would argue that this is misleading, as what one canonically calls the "Worst case" is again different; consider QuickSort, which is O(n^2) in the worst case (an already ordered input, or one that is otherwise pathological with respect to selection of the pivot), but O(n lg n) in the average case (a relatively-random distribution in the input's order). There are other common notations for related concepts. Omega is often used for describing lower bounds, and Theta for what CLRS call "tight" bounds, which we may think of as the infimum of O. Note that these notions predate computer science by some time. Hardy defined all three rigorously in "A Course of Pure Mathematics" (1908), using O() in the conventional sense, though he used "o" and "~" for omega and theta, respectively. These are useful in different fields of analysis (among other places). - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-11 09:04 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86a4v9a3fn.fsf@linuxsc.com> |
| In reply to | #397452 |
cross@spitfire.i.gajendra.net (Dan Cross) writes: > In article <86y0iyvypl.fsf@linuxsc.com>, > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >> >>> On Mon, 06 Apr 2026 21:00:46 -0700 >>> 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. >>> >>> So, how do you call part of the curve from 1e2 to 3e5 lines? MiddleO ? >> >> Consider a thought experiment. We have a qsort-like sorting function, >> for the sake of discussion let's say it uses heapsort. It is widely >> understood that heapsort is an O(N*log(N)) algorithm (not counting the >> theoretical objections mentioned in Waldek Hebisch's post and my >> response to those comments). >> >> Now suppose we have two distinct invocations of said function. In >> both cases the arguments are length 1000 character strings, having >> only spaces and alphabetic characters, and no duplicates between the >> strings. In one call all the strings have distinct values in the >> first six characters, and in the other call the strings are all the >> same in the first 993 characters, differing only in the last six >> characters. The call to the sorting function points back to a >> function that uses strcmp() to do its comparisons. >> >> The heapsort algorithm is well-known to be N log N. All the strings >> in both sorts are exactly 1000 characters, so the strcmp() calls have >> a fixed maximum time cost. And yet one of these sorts runs almost 200 >> times as fast as the other. >> >> I think what you're seeing is a data dependency that is orthogonal to >> the time complexity of the algorithm. For example, the travelling >> salesman problem is widely known to be NP complete, and yet on some >> inputs a solution can be found very quickly. > > A useful thought experiment, but it is perhaps easier to explain > that the asymptotic time complexity of a sorting algorithm, for > example heapsort being O(n log n), is expressed in terms of the > number of comparison operations required by the algorithm, > independent of the complexity of those comparisons. No. This misses the essence of what I was trying to convey. >> BigO is about worst case behavior, or sometimes average case >> behavior. Other kinds of behavior can depend dramatically on the >> nature of the inputs. > > I disagree with this. The "Big-O" of an algorithm isn't about > worst-case behavior, it's a notation for categorizing which term > dominates in an expression describing the complexity of an > algorithm, as the number of inputs to that algorithm grows. You misunderstood the point of my comment. Of course O() notation is about expressing an asymptotic upper bound of some function. The key issue here though is not about O() but about what function should be the one under consideration.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-11 19:55 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10re8uu$4pb$1@reader1.panix.com> |
| In reply to | #397487 |
In article <86a4v9a3fn.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >cross@spitfire.i.gajendra.net (Dan Cross) writes: > >> In article <86y0iyvypl.fsf@linuxsc.com>, >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> >>> Michael S <already5chosen@yahoo.com> writes: >>> >>>> On Mon, 06 Apr 2026 21:00:46 -0700 >>>> 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. >>>> >>>> So, how do you call part of the curve from 1e2 to 3e5 lines? MiddleO ? >>> >>> Consider a thought experiment. We have a qsort-like sorting function, >>> for the sake of discussion let's say it uses heapsort. It is widely >>> understood that heapsort is an O(N*log(N)) algorithm (not counting the >>> theoretical objections mentioned in Waldek Hebisch's post and my >>> response to those comments). >>> >>> Now suppose we have two distinct invocations of said function. In >>> both cases the arguments are length 1000 character strings, having >>> only spaces and alphabetic characters, and no duplicates between the >>> strings. In one call all the strings have distinct values in the >>> first six characters, and in the other call the strings are all the >>> same in the first 993 characters, differing only in the last six >>> characters. The call to the sorting function points back to a >>> function that uses strcmp() to do its comparisons. >>> >>> The heapsort algorithm is well-known to be N log N. All the strings >>> in both sorts are exactly 1000 characters, so the strcmp() calls have >>> a fixed maximum time cost. And yet one of these sorts runs almost 200 >>> times as fast as the other. >>> >>> I think what you're seeing is a data dependency that is orthogonal to >>> the time complexity of the algorithm. For example, the travelling >>> salesman problem is widely known to be NP complete, and yet on some >>> inputs a solution can be found very quickly. >> >> A useful thought experiment, but it is perhaps easier to explain >> that the asymptotic time complexity of a sorting algorithm, for >> example heapsort being O(n log n), is expressed in terms of the >> number of comparison operations required by the algorithm, >> independent of the complexity of those comparisons. > >No. This misses the essence of what I was trying to convey. Then what you are trying to convey is misleading. Note that I was making factual statements. >>> BigO is about worst case behavior, or sometimes average case >>> behavior. Other kinds of behavior can depend dramatically on the >>> nature of the inputs. >> >> I disagree with this. The "Big-O" of an algorithm isn't about >> worst-case behavior, it's a notation for categorizing which term >> dominates in an expression describing the complexity of an >> algorithm, as the number of inputs to that algorithm grows. > >You misunderstood the point of my comment. Of course O() >notation is about expressing an asymptotic upper bound of >some function. The key issue here though is not about O() >but about what function should be the one under consideration. The misunderstanding is yours, I'm afraid. You wrote, "BigO is about worst case behavior." That is definitionally incorrect, and it's not really something that is up for debate or open to alternative interpretations. If you want to account for the complexity of a comparison function, and you can characterize it in some useful, way, you can of course incorporate that into the analysis. For example, string comparison is linear in the size of the input strings; if one denotes that as m, then the time required to sort strings using heapsort might be described is O(m*n*log(n)) - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | antispam@fricas.org (Waldek Hebisch) |
|---|---|
| Date | 2026-04-07 14:46 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10r35bp$29m9s$1@paganini.bofh.team> |
| In reply to | #397405 |
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.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-07 20:04 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <863416xid5.fsf@linuxsc.com> |
| In reply to | #397412 |
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. 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.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-09 21:15 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10r94t2$or8$1@reader1.panix.com> |
| In reply to | #397417 |
In article <863416xid5.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: >> >>> 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. > >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. If by "Knuth's books" you're referring to TAOCP, then he does not seem to give it too much attention. At the start of Volume 3, he spends considerable time discussing the combinatorics of permutations as prefatory to discussing sorting, but if he talks about the complexity of key comparison at all, it's not an extended treatment. He refers to a "<" operation for comparing keys, and he does talk about "multiprecision keys" and lexiographic orderings, but doesn't spend a lot of ink talking about how it might be implemented; one of the exercises acknowledges that this can have a significant impact on performance, but doesn't go into much detail. Another excise challenges the reader to write a MIX program for comparing keys, but again, doesn't give details about complexity analysis _of comparison_. There is another exercise that talks about this tangentially, in which he suggests sorting (it's kind of implied of text data) slows down as the sort nears completion, since more and more of the key value is now the same, and suggests keeping track of the length of the common prefix to use as an offset for subsequent comparisons. I have seen the notion that the actual time required for individual operations should be taken into account when analyzing their time complexity does appear in other books; Dasgupta, Papadimitriou, and Vazirani (http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf) talk about this in the context of computing Fibonacci numbers, for example. >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. Indeed. As Rob Pike once put it, "Fancy algorithms are slow when $n$ is small, and $n$ is usually small. Fancy algorithms have big constants. Until you know that $n$ is frequently going to get big, don't get fancy." - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-10 01:31 +0300 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260410013139.000059d4@yahoo.com> |
| In reply to | #397454 |
On Thu, 9 Apr 2026 21:15:14 -0000 (UTC) cross@spitfire.i.gajendra.net (Dan Cross) wrote: > In article <863416xid5.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: > >> > >>> 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. > > > >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. > > If by "Knuth's books" you're referring to TAOCP, then he does > not seem to give it too much attention. At the start of Volume > 3, he spends considerable time discussing the combinatorics of > permutations as prefatory to discussing sorting, but if he talks > about the complexity of key comparison at all, it's not an > extended treatment. He refers to a "<" operation for comparing > keys, and he does talk about "multiprecision keys" and > lexiographic orderings, but doesn't spend a lot of ink talking > about how it might be implemented; one of the exercises > acknowledges that this can have a significant impact on > performance, but doesn't go into much detail. Another excise > challenges the reader to write a MIX program for comparing keys, > but again, doesn't give details about complexity analysis _of > comparison_. There is another exercise that talks about this > tangentially, in which he suggests sorting (it's kind of implied > of text data) slows down as the sort nears completion, since > more and more of the key value is now the same, and suggests > keeping track of the length of the common prefix to use as an > offset for subsequent comparisons. > > I have seen the notion that the actual time required for > individual operations should be taken into account when > analyzing their time complexity does appear in other books; > Dasgupta, Papadimitriou, and Vazirani > (http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf) > talk about this in the context of computing Fibonacci numbers, > for example. > > >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. > > Indeed. As Rob Pike once put it, "Fancy algorithms are slow > when $n$ is small, and $n$ is usually small. Fancy algorithms > have big constants. Until you know that $n$ is frequently going > to get big, don't get fancy." > > - Dan C. > One case where these considerations are not at all theoretical and where simple quicksort from the books performs very very slowly exactly because when sorting progresses each lexicographic comparison takes more and more time, is a sorting at core of Burrows–Wheeler transform, which in turn is at core of various compression schemes, including bzip2. The problem hits you the worst when data set compresses well. In specific case of bzip2, they limited block size to 900KB which is quite low and did preprocessing on input data which often seriously impacts the quality of compression. I can't say for sure, but it seems to me that the reason was exactly that - avoiding prohibitively slow sorting. Were they had time and desire to use "fancy algorithms", either combinations of bucket and non-bucket variants of radix sort, or quicksort that memorizes common prefixes, or even combination of all three, then they would not need to use preprocessing and small blocks and would end up with better compression ratios.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-12 06:17 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86wlyc8giv.fsf@linuxsc.com> |
| In reply to | #397455 |
Michael S <already5chosen@yahoo.com> writes: > On Thu, 9 Apr 2026 21:15:14 -0000 (UTC) > cross@spitfire.i.gajendra.net (Dan Cross) wrote: [...] >> Indeed. As Rob Pike once put it, "Fancy algorithms are slow >> when $n$ is small, and $n$ is usually small. Fancy algorithms >> have big constants. Until you know that $n$ is frequently going >> to get big, don't get fancy." > > One case where these considerations are not at all theoretical and > where simple quicksort from the books performs very very slowly exactly > because when sorting progresses each lexicographic comparison > takes more and more time, is a sorting at core of Burrows-Wheeler > transform, which in turn is at core of various compression schemes, > including bzip2. The problem hits you the worst when data set compresses > well. I'm curious to know if you can quantify this to some degree, and if so how much. I don't have any experience with Burrows-Wheeler transform or (any internals of) bzip2. > In specific case of bzip2, they limited block size to 900KB which > is quite low and did preprocessing on input data which often seriously > impacts the quality of compression. I can't say for sure, but it seems > to me that the reason was exactly that - avoiding prohibitively slow > sorting. Were they had time and desire to use "fancy algorithms", > either combinations of bucket and non-bucket variants of radix sort, or > quicksort that memorizes common prefixes, or even combination of all > three, then they would not need to use preprocessing and small blocks > and would end up with better compression ratios. There could be other reasons for wanting to limit the block size. Have you done any web searches or tried to investigate in some other ways?
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-11 21:32 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <861pgkaje2.fsf@linuxsc.com> |
| In reply to | #397454 |
cross@spitfire.i.gajendra.net (Dan Cross) writes: > In article <863416xid5.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: >>> >>>> 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. >> >> 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. > > If by "Knuth's books" you're referring to TAOCP, then he does > not seem to give it too much attention. [...] In most of the chapter on Sorting, TAOCP uses the number of comparisons as the basis of comparison. But not everywhere in the chapter. My statement was not meant to be limited to the discussion of Sorting. >> 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. > > Indeed. As Rob Pike once put it, "Fancy algorithms are slow > when $n$ is small, and $n$ is usually small. Fancy algorithms > have big constants. Until you know that $n$ is frequently going > to get big, don't get fancy." Whether the Rob Pike advisory is applicable or not is beside the point. My comment was about fancy mathematics, not fancy algorithms. My statement is just as applicable to Tim Sort (one of the fancier sorting algorithms) as it is to Bubble Sort.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-12 04:59 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10rf8rr$j50$1@reader1.panix.com> |
| In reply to | #397497 |
In article <861pgkaje2.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >cross@spitfire.i.gajendra.net (Dan Cross) writes: >> In article <863416xid5.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: >>>>> 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. >>> >>> 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. >> >> If by "Knuth's books" you're referring to TAOCP, then he does >> not seem to give it too much attention. [...] > >In most of the chapter on Sorting, TAOCP uses the number of >comparisons as the basis of comparison. But not everywhere >in the chapter. It seems like I pointed out a few places where he acknowledges a more complex picture. Are there other places to which you are referring? >My statement was not meant to be limited to the discussion of >Sorting. What do you think I was referring to, exactly? I was responding to your comments about Knuth's books, specifically, and the quoted text above, which seems concerned solely with sorting. As I mentioned, Dasgupta et al _do_ mention that analysis of algorithms is more complex than most treatments, because of precisely the idea that as things grow, seemingly constant operations are no longer constant. As I mentioned, they did this within the context of Fibonacci numbers, not sorting, but the point stands. Since, as you say, your statement was not meant to be limited to discussions of sorting, then it seems to be supporting what you are saying. >>> 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. >> >> Indeed. As Rob Pike once put it, "Fancy algorithms are slow >> when $n$ is small, and $n$ is usually small. Fancy algorithms >> have big constants. Until you know that $n$ is frequently going >> to get big, don't get fancy." > >Whether the Rob Pike advisory is applicable or not is beside the >point. On the contrary; I mentioned it because it supports your thesis. >My comment was about fancy mathematics, not fancy >algorithms. My statement is just as applicable to Tim Sort (one >of the fancier sorting algorithms) as it is to Bubble Sort. There's nothing particularly fancy about it, but that aside, I'm honestly not sure what exactly I said that you are (apparently?) disagreeing with. I was responding with a specific statement about Knuth's books, a reference to another book in support of your statement, and yet another reference to something that Pike had written that, again, supports your point. - Dan C.
[toc] | [prev] | [next] | [standalone]
Page 8 of 12 — ← Prev page 1 … 6 7 [8] 9 10 … 12 Next page →
Back to top | Article view | comp.lang.c
csiph-web