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 9 of 12 — ← Prev page 1 … 7 8 [9] 10 11 12 Next page →
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-26 07:29 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86340h3idt.fsf@linuxsc.com> |
| In reply to | #397498 |
cross@spitfire.i.gajendra.net (Dan Cross) writes: > 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. I read through your comments. My sense is there are still some misunderstandings (probably on both sides) but I think it's probably better just to leave it at that. Also the discussion has wandered kind of far afield for comp.lang.c, so in the interest of courtesy I am stopping here, except to add thank you for your comments.
[toc] | [prev] | [next] | [standalone]
| From | antispam@fricas.org (Waldek Hebisch) |
|---|---|
| Date | 2026-04-09 23:33 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10r9d06$32585$1@paganini.bofh.team> |
| In reply to | #397417 |
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> antispam@fricas.org (Waldek Hebisch) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> Michael S <already5chosen@yahoo.com> writes:
>>>
>>>> On Mon, 06 Apr 2026 15:13:32 -0700
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>>
>>>>> Obviously what words (or lines) appear can affect the character
>>>>> counts, but that still doesn't change BigO. By the way you don't
>>>>> say whether you are sorting words or lines.
>>>>
>>>> This sub-thread is about sorting lines with average length of few
>>>> dozens characters, i.e. many times longer than log2(N). That was
>>>> stated at one of earlier posts.
>>>
>>> That has nothing to do with BigO, which is about asymptotic
>>> behavior as N goes to infinity.
>>
>> Honest Big(O) varies length of the key with N. In practical range
>> key length may be constant, but fixing length gives unrealistic
>> problem for Big(O) analysis: without varying key length there are
>> finitely many keys and sorting is equivalent to counting how many
>> times each key appears in the input.
>
> There's an important clarification to make here. There are two
> independent parameters: N, the number of records to be sorted (a
> record being a character string that is either a word or a line),
> and the (maximum) length of any record, which in the discussion is
> bounded above by a constant.
There is one choice, made often to simplify problem. But there
is quite universal choice: N is total size of input data.
> What is being asked about is the behavior as a function of N as N
> increases without bound. Of course, theoretically, as the number of
> records increases without bound, eventually the character strings
> being sorted will have to have duplicates. But long before that
> happens the index variable N will run out of bits. This property is
> well understood in theoretical computer science, not just in terms
> of how much time is used but how much storage is needed. In theory
> log N bits are needed just to hold the index pointers. It is
> customary though, outside of purely theoretical discussions, to
> ignore that and treat the size of an index or pointer variable as
> constant. In purely theoretical terms no sorting algorithm is
> O(N*log(N)), because just incrementing a pointer takes more than
> O(1) operations. Surely the discussions in Knuth's books take such
> things into consideration. On the practical side, which almost
> always covers discussions that take place in usenet newsgroups,
> these minor theoretical issues are ignored. Any actul computer in
> the physical universe will never have occasion to process more than
> 2**512 records, due to the limitation of the number of elementary
> particles in the universe, so a 512-bit address (or index value)
> always suffices.
>
> So yes, in theory, the considerations around processing an enormous
> number of values are relevant. In the practical context of the
> discussion underway here, they aren't.
It was you who insisted on asymptitic complexity, rejecting
practical amendments...
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-10 11:35 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10ranaa$ihf$1@reader1.panix.com> |
| In reply to | #397456 |
In article <10r9d06$32585$1@paganini.bofh.team>, Waldek Hebisch <antispam@fricas.org> wrote: >Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> antispam@fricas.org (Waldek Hebisch) writes: >> >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> Michael S <already5chosen@yahoo.com> writes: >>>> >>>>> On Mon, 06 Apr 2026 15:13:32 -0700 >>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>> >>>>>> Obviously what words (or lines) appear can affect the character >>>>>> counts, but that still doesn't change BigO. By the way you don't >>>>>> say whether you are sorting words or lines. >>>>> >>>>> This sub-thread is about sorting lines with average length of few >>>>> dozens characters, i.e. many times longer than log2(N). That was >>>>> stated at one of earlier posts. >>>> >>>> That has nothing to do with BigO, which is about asymptotic >>>> behavior as N goes to infinity. >>> >>> Honest Big(O) varies length of the key with N. In practical range >>> key length may be constant, but fixing length gives unrealistic >>> problem for Big(O) analysis: without varying key length there are >>> finitely many keys and sorting is equivalent to counting how many >>> times each key appears in the input. >> >> There's an important clarification to make here. There are two >> independent parameters: N, the number of records to be sorted (a >> record being a character string that is either a word or a line), >> and the (maximum) length of any record, which in the discussion is >> bounded above by a constant. > >There is one choice, made often to simplify problem. But there >is quite universal choice: N is total size of input data. This is too simplistic. Analysis of sorting algorithms treats $n$ as the number of input _records_, only considering their size tangentially. In turn, records are distinguished by having some kind of "key" and the existence of some comparison operator, "<", that obeys the usual ordering properties of mathematics. Sorting involves establishing an order for some collection of records, <R_1, ..., R_n> so that R_1 < R_2 < ... < R_n. When we say, O(n lg n), we are referring to the number of comparisons required. If the comparison function itself is complex, specifically if it is non-constant, is an entirely separate matter. "Total size of input data" doesn't enter into it at at all; indeed, it doesn't even make much sense conceptually: suppose I have some sequence of large records, but the key is just a fixed size integer in that record. Then the comparison is cheap; probably just a single machine instruction on real computers, despite the data itself being large. "Aha, but what about the cost of moving data within such a sequence? If the records are large, that's non-trivial and you must account for that." Indeed, this can be an issue; often one works around it by holding an auxiliary array of pointers to the records themselves, and sorting those. Again, exchanges here are cheap: just a handful of machine instructions. Do real-world programmers care about the actual cost of both the comparison function _and_ moving data around to exchange elements in e.g., an array when sorting? Absolutely. But trying to shoehorn those concerns into big-O notation is not a useful exercise in accounting for them. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-12 07:13 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86fr508dwq.fsf@linuxsc.com> |
| In reply to | #397456 |
antispam@fricas.org (Waldek Hebisch) writes: > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> antispam@fricas.org (Waldek Hebisch) writes: >> >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> Michael S <already5chosen@yahoo.com> writes: >>>> >>>>> On Mon, 06 Apr 2026 15:13:32 -0700 >>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>> >>>>>> Obviously what words (or lines) appear can affect the character >>>>>> counts, but that still doesn't change BigO. By the way you don't >>>>>> say whether you are sorting words or lines. >>>>> >>>>> This sub-thread is about sorting lines with average length of few >>>>> dozens characters, i.e. many times longer than log2(N). That was >>>>> stated at one of earlier posts. >>>> >>>> That has nothing to do with BigO, which is about asymptotic >>>> behavior as N goes to infinity. >>> >>> Honest Big(O) varies length of the key with N. In practical range >>> key length may be constant, but fixing length gives unrealistic >>> problem for Big(O) analysis: without varying key length there are >>> finitely many keys and sorting is equivalent to counting how many >>> times each key appears in the input. >> >> There's an important clarification to make here. There are two >> independent parameters: N, the number of records to be sorted (a >> record being a character string that is either a word or a line), >> and the (maximum) length of any record, which in the discussion is >> bounded above by a constant. > > There is one choice, made often to simplify problem. But there > is quite universal choice: N is total size of input data. No, N is usually the number of records to be sorted, not the size of the input. Also, in the discussion I was responding to, there were clearly two distinct axes relevant to the discussion. >> What is being asked about is the behavior as a function of N as N >> increases without bound. Of course, theoretically, as the number of >> records increases without bound, eventually the character strings >> being sorted will have to have duplicates. But long before that >> happens the index variable N will run out of bits. This property is >> well understood in theoretical computer science, not just in terms >> of how much time is used but how much storage is needed. In theory >> log N bits are needed just to hold the index pointers. It is >> customary though, outside of purely theoretical discussions, to >> ignore that and treat the size of an index or pointer variable as >> constant. In purely theoretical terms no sorting algorithm is >> O(N*log(N)), because just incrementing a pointer takes more than >> O(1) operations. Surely the discussions in Knuth's books take such >> things into consideration. On the practical side, which almost >> always covers discussions that take place in usenet newsgroups, >> these minor theoretical issues are ignored. Any actul computer in >> the physical universe will never have occasion to process more than >> 2**512 records, due to the limitation of the number of elementary >> particles in the universe, so a 512-bit address (or index value) >> always suffices. >> >> So yes, in theory, the considerations around processing an enormous >> number of values are relevant. In the practical context of the >> discussion underway here, they aren't. > > It was you who insisted on asymptitic complexity, rejecting > practical amendments... This statement isn't right. BigO was already part of the discussion when I joined in. Also, it is customary in discussion of sorting algorithms to use the metric of number of comparisons done, without regard to the size of the variables needed to hold the indices of the records being sorted. See Knuth chapter 5, on Sorting, in volume 3 of TAOCP.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-13 20:44 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10rjkin$otp$1@reader1.panix.com> |
| In reply to | #397505 |
In article <86fr508dwq.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >antispam@fricas.org (Waldek Hebisch) writes: >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> antispam@fricas.org (Waldek Hebisch) writes: >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>> Michael S <already5chosen@yahoo.com> writes: >>>>>> On Mon, 06 Apr 2026 15:13:32 -0700 >>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>>> >>>>>>> Obviously what words (or lines) appear can affect the character >>>>>>> counts, but that still doesn't change BigO. By the way you don't >>>>>>> say whether you are sorting words or lines. >>>>>> >>>>>> This sub-thread is about sorting lines with average length of few >>>>>> dozens characters, i.e. many times longer than log2(N). That was >>>>>> stated at one of earlier posts. >>>>> >>>>> That has nothing to do with BigO, which is about asymptotic >>>>> behavior as N goes to infinity. >>>> >>>> Honest Big(O) varies length of the key with N. In practical range >>>> key length may be constant, but fixing length gives unrealistic >>>> problem for Big(O) analysis: without varying key length there are >>>> finitely many keys and sorting is equivalent to counting how many >>>> times each key appears in the input. >>> >>> There's an important clarification to make here. There are two >>> independent parameters: N, the number of records to be sorted (a >>> record being a character string that is either a word or a line), >>> and the (maximum) length of any record, which in the discussion is >>> bounded above by a constant. >> >> There is one choice, made often to simplify problem. But there >> is quite universal choice: N is total size of input data. > >No, N is usually the number of records to be sorted, not the size of >the input. Also, in the discussion I was responding to, there were >clearly two distinct axes relevant to the discussion. > >>> What is being asked about is the behavior as a function of N as N >>> increases without bound. Of course, theoretically, as the number of >>> records increases without bound, eventually the character strings >>> being sorted will have to have duplicates. But long before that >>> happens the index variable N will run out of bits. This property is >>> well understood in theoretical computer science, not just in terms >>> of how much time is used but how much storage is needed. In theory >>> log N bits are needed just to hold the index pointers. It is >>> customary though, outside of purely theoretical discussions, to >>> ignore that and treat the size of an index or pointer variable as >>> constant. In purely theoretical terms no sorting algorithm is >>> O(N*log(N)), because just incrementing a pointer takes more than >>> O(1) operations. Surely the discussions in Knuth's books take such >>> things into consideration. On the practical side, which almost >>> always covers discussions that take place in usenet newsgroups, >>> these minor theoretical issues are ignored. Any actul computer in >>> the physical universe will never have occasion to process more than >>> 2**512 records, due to the limitation of the number of elementary >>> particles in the universe, so a 512-bit address (or index value) >>> always suffices. >>> >>> So yes, in theory, the considerations around processing an enormous >>> number of values are relevant. In the practical context of the >>> discussion underway here, they aren't. >> >> It was you who insisted on asymptitic complexity, rejecting >> practical amendments... > >This statement isn't right. BigO was already part of the discussion >when I joined in. Also, it is customary in discussion of sorting >algorithms to use the metric of number of comparisons done, without >regard to the size of the variables needed to hold the indices of >the records being sorted. Hmm, this response echoes almost exactly what I wrote in <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in response to Waldek. Did you see it? >See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. As for TAOCP, as much as I respect and admire Knuth, I don't think "The Art of Computer Programming" is a good reference for working programmers. At 391 pages long, Chapter Five occupies more than half of an ~750 page book, the examples are all in assembly language for his notional MIX computer, and the analysis he presents presumes a mathematics background that, frankly, most programmers neither have nor need. "See chapter 5" is thus not useful as a reference, and rather comes across as an admonishment. A much more useful treatment is Cormen, Leiserson, Rivest, and Stein's, "Introduction to Algorithms." The treatment is much more accessible than TAOCP, while still rigorous. Disclaimer: I once served as a industry mentor for students taking one of Leiserson's classes, though I haven't worked with him closely. CLRS suggests that Aho, Hopcroft, and Ullman advocated for asymptotic analysis of algorithms in, "The Design and Analysis of Computer Algorithms". Again, it's a wonderful book, but I would argue it's more theoretical than most programmers would find comfortable. Disclaimer: Aho taught me compilers. Personally, I like Skiena's, "Algorithm Design Manual" and think that its treatment is among the best I've seen when it comes to threading the needle between rigorous attention to detail and accessibility, though one needs more mathematics to negotiate it than e.g., CLRS. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-25 15:47 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86fr4i3ben.fsf@linuxsc.com> |
| In reply to | #397520 |
cross@spitfire.i.gajendra.net (Dan Cross) writes: > In article <86fr508dwq.fsf@linuxsc.com>, > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> antispam@fricas.org (Waldek Hebisch) writes: >> >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> antispam@fricas.org (Waldek Hebisch) writes: >>>> >>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>> >>>>>> Michael S <already5chosen@yahoo.com> writes: >>>>>> >>>>>>> On Mon, 06 Apr 2026 15:13:32 -0700 >>>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>>>>>> >>>>>>>> Obviously what words (or lines) appear can affect the character >>>>>>>> counts, but that still doesn't change BigO. By the way you don't >>>>>>>> say whether you are sorting words or lines. >>>>>>> >>>>>>> This sub-thread is about sorting lines with average length of few >>>>>>> dozens characters, i.e. many times longer than log2(N). That was >>>>>>> stated at one of earlier posts. >>>>>> >>>>>> That has nothing to do with BigO, which is about asymptotic >>>>>> behavior as N goes to infinity. >>>>> >>>>> Honest Big(O) varies length of the key with N. In practical range >>>>> key length may be constant, but fixing length gives unrealistic >>>>> problem for Big(O) analysis: without varying key length there are >>>>> finitely many keys and sorting is equivalent to counting how many >>>>> times each key appears in the input. >>>> >>>> There's an important clarification to make here. There are two >>>> independent parameters: N, the number of records to be sorted (a >>>> record being a character string that is either a word or a line), >>>> and the (maximum) length of any record, which in the discussion is >>>> bounded above by a constant. >>> >>> There is one choice, made often to simplify problem. But there >>> is quite universal choice: N is total size of input data. >> >> No, N is usually the number of records to be sorted, not the size of >> the input. Also, in the discussion I was responding to, there were >> clearly two distinct axes relevant to the discussion. >> >>>> What is being asked about is the behavior as a function of N as N >>>> increases without bound. Of course, theoretically, as the number of >>>> records increases without bound, eventually the character strings >>>> being sorted will have to have duplicates. But long before that >>>> happens the index variable N will run out of bits. This property is >>>> well understood in theoretical computer science, not just in terms >>>> of how much time is used but how much storage is needed. In theory >>>> log N bits are needed just to hold the index pointers. It is >>>> customary though, outside of purely theoretical discussions, to >>>> ignore that and treat the size of an index or pointer variable as >>>> constant. In purely theoretical terms no sorting algorithm is >>>> O(N*log(N)), because just incrementing a pointer takes more than >>>> O(1) operations. Surely the discussions in Knuth's books take such >>>> things into consideration. On the practical side, which almost >>>> always covers discussions that take place in usenet newsgroups, >>>> these minor theoretical issues are ignored. Any actul computer in >>>> the physical universe will never have occasion to process more than >>>> 2**512 records, due to the limitation of the number of elementary >>>> particles in the universe, so a 512-bit address (or index value) >>>> always suffices. >>>> >>>> So yes, in theory, the considerations around processing an enormous >>>> number of values are relevant. In the practical context of the >>>> discussion underway here, they aren't. >>> >>> It was you who insisted on asymptitic complexity, rejecting >>> practical amendments... >> >> This statement isn't right. BigO was already part of the discussion >> when I joined in. Also, it is customary in discussion of sorting >> algorithms to use the metric of number of comparisons done, without >> regard to the size of the variables needed to hold the indices of >> the records being sorted. > > Hmm, this response echoes almost exactly what I wrote in > <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in > response to Waldek. Did you see it? Probably, but I don't remember it specifically. >> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. > > As for TAOCP, as much as I respect and admire Knuth, I don't > think "The Art of Computer Programming" is a good reference for > working programmers. At 391 pages long, Chapter Five occupies > more than half of an ~750 page book, the examples are all in > assembly language for his notional MIX computer, and the > analysis he presents presumes a mathematics background that, > frankly, most programmers neither have nor need. I am not recommending TAOCP as a textbook. It's a well-known work and respected for its theoretical treatments. Also it happens to be what I consulted before posting, mainly because it was handy. > "See chapter 5" is thus not useful as a reference, and rather > comes across as an admonishment. No admonishment was intented. I mentioned it only as a supporting work for my previous statement.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-27 02:04 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10smg7d$iad$1@reader1.panix.com> |
| In reply to | #397953 |
In article <86fr4i3ben.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >cross@spitfire.i.gajendra.net (Dan Cross) writes: >> In article <86fr508dwq.fsf@linuxsc.com>, >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> antispam@fricas.org (Waldek Hebisch) writes: >>>> [snip] >>>> There is one choice, made often to simplify problem. But there >>>> is quite universal choice: N is total size of input data. >>> >>> No, N is usually the number of records to be sorted, not the size of >>> the input. Also, in the discussion I was responding to, there were >>> clearly two distinct axes relevant to the discussion. >>> >>>>> What is being asked about is the behavior as a function of N as N >>>>> increases without bound. Of course, theoretically, as the number of >>>>> records increases without bound, eventually the character strings >>>>> being sorted will have to have duplicates. But long before that >>>>> happens the index variable N will run out of bits. This property is >>>>> well understood in theoretical computer science, not just in terms >>>>> of how much time is used but how much storage is needed. In theory >>>>> log N bits are needed just to hold the index pointers. It is >>>>> customary though, outside of purely theoretical discussions, to >>>>> ignore that and treat the size of an index or pointer variable as >>>>> constant. In purely theoretical terms no sorting algorithm is >>>>> O(N*log(N)), because just incrementing a pointer takes more than >>>>> O(1) operations. Surely the discussions in Knuth's books take such >>>>> things into consideration. On the practical side, which almost >>>>> always covers discussions that take place in usenet newsgroups, >>>>> these minor theoretical issues are ignored. Any actul computer in >>>>> the physical universe will never have occasion to process more than >>>>> 2**512 records, due to the limitation of the number of elementary >>>>> particles in the universe, so a 512-bit address (or index value) >>>>> always suffices. >>>>> >>>>> So yes, in theory, the considerations around processing an enormous >>>>> number of values are relevant. In the practical context of the >>>>> discussion underway here, they aren't. >>>> >>>> It was you who insisted on asymptitic complexity, rejecting >>>> practical amendments... >>> >>> This statement isn't right. BigO was already part of the discussion >>> when I joined in. Also, it is customary in discussion of sorting >>> algorithms to use the metric of number of comparisons done, without >>> regard to the size of the variables needed to hold the indices of >>> the records being sorted. >> >> Hmm, this response echoes almost exactly what I wrote in >> <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in >> response to Waldek. Did you see it? > >Probably, but I don't remember it specifically. Very well. >>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. >> >> As for TAOCP, as much as I respect and admire Knuth, I don't >> think "The Art of Computer Programming" is a good reference for >> working programmers. At 391 pages long, Chapter Five occupies >> more than half of an ~750 page book, the examples are all in >> assembly language for his notional MIX computer, and the >> analysis he presents presumes a mathematics background that, >> frankly, most programmers neither have nor need. > >I am not recommending TAOCP as a textbook. No, but you are referring to it and suggesting that someone else do the same; ie, using it as a reference and giving it to another as a reference. >It's a well-known work >and respected for its theoretical treatments. Also it happens to be >what I consulted before posting, mainly because it was handy. What part? As I mentioned, "Chapter 5" of TAOCP is nearly 400 pages long, and touches on a great many things. It's not at all clear what precisely, from that book-length chapter, you may be referring to. Further, "See Knuth chapter 5" is an imperative statement, not a statement of fact about something you had done. My point is that, if your goal is to a establish shared working vocabulary with Waldek, such a directive is, unfortunately, not likely to be particularly useful towards that goal. >> "See chapter 5" is thus not useful as a reference, and rather >> comes across as an admonishment. > >No admonishment was intented. I mentioned it only as a supporting >work for my previous statement. My point is that the statement is too vague. A more useful citation would be to a section, or perhaps a page number, edition, and printing, or perhaps a direct quotation. Absent a more refined citation, the reference to Knuth comes across as more of an appeal to authority than something that is actually meant to illuminate the discussion. I trust you that that was Not your intent, however. I do think this is actually useful, even in the context of comp.lang.c; a lot of people posting here seem to have forgotten many of the finer points of analyzing the characteristics of the code that is frequently under discussion, and understanding how to apply such to C code is an important skill. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-26 22:27 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86v7dd0y8j.fsf@linuxsc.com> |
| In reply to | #398023 |
cross@spitfire.i.gajendra.net (Dan Cross) writes: > In article <86fr4i3ben.fsf@linuxsc.com>, > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> cross@spitfire.i.gajendra.net (Dan Cross) writes: >> >>> In article <86fr508dwq.fsf@linuxsc.com>, >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: [..trimming some earlier portions..] >>>> [...] BigO was already part of the discussion >>>> when I joined in. Also, it is customary in discussion of sorting >>>> algorithms to use the metric of number of comparisons done, without >>>> regard to the size of the variables needed to hold the indices of >>>> the records being sorted. >>> >>> Hmm, this response echoes almost exactly what I wrote in >>> <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in >>> response to Waldek. Did you see it? >> >> Probably, but I don't remember it specifically. > > Very well. > >>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. >>> >>> As for TAOCP, as much as I respect and admire Knuth, I don't >>> think "The Art of Computer Programming" is a good reference for >>> working programmers. At 391 pages long, Chapter Five occupies >>> more than half of an ~750 page book, the examples are all in >>> assembly language for his notional MIX computer, and the >>> analysis he presents presumes a mathematics background that, >>> frankly, most programmers neither have nor need. >> >> I am not recommending TAOCP as a textbook. > > No, but you are referring to it and suggesting that someone else > do the same; ie, using it as a reference and giving it to > another as a reference. I said this: >>>> Also, it is customary in discussion of sorting algorithms to use >>>> the metric of number of comparisons done, without regard to the >>>> size of the variables needed to hold the indices of the records >>>> being sorted. I then said this: >>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. This chapter in TAOCP discusses sorting algorithms. Most of the discussion uses the number of comparisons needed, as a function of the number of records to be sorted (and only that) in characterizing the different algorithms. >> It's a well-known work >> and respected for its theoretical treatments. Also it happens to be >> what I consulted before posting, mainly because it was handy. > > What part? As I mentioned, "Chapter 5" of TAOCP is nearly 400 > pages long, and touches on a great many things. It's not at all > clear what precisely, from that book-length chapter, you may be > referring to. Most of the discussion in that chapter. > Further, "See Knuth chapter 5" is an imperative statement, not a > statement of fact about something you had done. > > My point is that, if your goal is to a establish shared working > vocabulary with Waldek, such a directive is, unfortunately, not > likely to be particularly useful towards that goal. My goal was only to support my statement "it is customary in discussion of sorting algorithms to use the metric of number of comparisons done [...]". No goal other than that. >>> "See chapter 5" is thus not useful as a reference, and rather >>> comes across as an admonishment. >> >> No admonishment was intented. I mentioned it only as a supporting >> work for my previous statement. > > My point is that the statement is too vague. A more useful > citation would be to a section, or perhaps a page number, > edition, and printing, or perhaps a direct quotation. I'm sorry you thought the statement was too vague. I thought it was clear enough when I wrote it. > Absent a more refined citation, the reference to Knuth comes > across as more of an appeal to authority than something that is > actually meant to illuminate the discussion. The reference to Knuth was only to support my earlier statement. I had thought that was evident. > I trust you that that was Not your intent, however. > > I do think this is actually useful, even in the context of > comp.lang.c; a lot of people posting here seem to have forgotten > many of the finer points of analyzing the characteristics of the > code that is frequently under discussion, and understanding how > to apply such to C code is an important skill. In any discussion it's important to keep in mind which details are essential to the discussion and which ones are better left out. It was my judgment that in the context of the post(s) I was responding to that the number of comparisons, as a function of the number of records to be sorted, was a key part of the discussion, but that more detailed analysis was unnecessary. Other people are free to have their own views on that question. However, for what I was trying to get across, I still think the level of detail I settled on was an appropriate choice for what I was hoping to convey.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2026-04-27 14:41 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10snsiv$oel$1@reader1.panix.com> |
| In reply to | #398025 |
In article <86v7dd0y8j.fsf@linuxsc.com>, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >cross@spitfire.i.gajendra.net (Dan Cross) writes: > >> In article <86fr4i3ben.fsf@linuxsc.com>, >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> >>> cross@spitfire.i.gajendra.net (Dan Cross) writes: >>> >>>> In article <86fr508dwq.fsf@linuxsc.com>, >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >[..trimming some earlier portions..] > >>>>> [...] BigO was already part of the discussion >>>>> when I joined in. Also, it is customary in discussion of sorting >>>>> algorithms to use the metric of number of comparisons done, without >>>>> regard to the size of the variables needed to hold the indices of >>>>> the records being sorted. >>>> >>>> Hmm, this response echoes almost exactly what I wrote in >>>> <10ranaa$ihf$1@reader1.panix.com> on April 10th, also in >>>> response to Waldek. Did you see it? >>> >>> Probably, but I don't remember it specifically. >> >> Very well. >> >>>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. >>>> >>>> As for TAOCP, as much as I respect and admire Knuth, I don't >>>> think "The Art of Computer Programming" is a good reference for >>>> working programmers. At 391 pages long, Chapter Five occupies >>>> more than half of an ~750 page book, the examples are all in >>>> assembly language for his notional MIX computer, and the >>>> analysis he presents presumes a mathematics background that, >>>> frankly, most programmers neither have nor need. >>> >>> I am not recommending TAOCP as a textbook. >> >> No, but you are referring to it and suggesting that someone else >> do the same; ie, using it as a reference and giving it to >> another as a reference. > >I said this: > >>>>> Also, it is customary in discussion of sorting algorithms to use >>>>> the metric of number of comparisons done, without regard to the >>>>> size of the variables needed to hold the indices of the records >>>>> being sorted. > >I then said this: > >>>>> See Knuth chapter 5, on Sorting, in volume 3 of TAOCP. That is using it as a reference. That's definitionally what making a reference to a text is. >This chapter in TAOCP discusses sorting algorithms. Yes. >Most of the >discussion uses the number of comparisons needed, as a function of >the number of records to be sorted (and only that) in characterizing >the different algorithms. Careful when you say "most of the discussion" here: discussion of the time complexity of the algorithms he discusses is written in those terms, true, but that is not all, or even most, of the discussion in the chapter. >>> It's a well-known work >>> and respected for its theoretical treatments. Also it happens to be >>> what I consulted before posting, mainly because it was handy. >> >> What part? As I mentioned, "Chapter 5" of TAOCP is nearly 400 >> pages long, and touches on a great many things. It's not at all >> clear what precisely, from that book-length chapter, you may be >> referring to. > >Most of the discussion in that chapter. No. I've read that chapter myself, and as I said, it covers a variety of material, little of which is actually germaine to the discussion you were having with Waldek. Much of the first 100 pages is devoted to the combinatorics of permutations of sets, for example; discussion of internal sorting doesn't begin until page 73 (2nd Ed). The emphasis on combinatorical analysis early on is necessary because significant attention is given to describing how the algorithms work, using combinatorics as a mathematically precise foundation. Furthermore, where he does discuss performance analysis of the early algorithms tends to be exact, using polynomials to precisely describe the number of MIX instructions used for each algorithm; it isn't until he gets to Shell's sort (infamously complex to analyze) that he really moves away from that in earnest; e.g., theorem P et al. Even then, he tends to eschew big-O notation and go deeper. For example, he says this about Radix exchange sort: "...the total running time comes to 27A + 8B + 8C - 23G - 14K - 17L - 19R - X + 13 units" (p.127), where each variable is defined in a preceding table. He then derives expected runtime and discusses, concluding with, "the corresponding figure for Program Q is 11.7 N ln N, which can be decreased to about 10.6 N ln N using Singleton's median-of-three suggestion." But importantly in this context, "N" is the number of records, not comparisons. This then leads into a more precise discussion of the mathematics behind the asymptotic behavior of functions, in which he applies techniques from complex analysis, deriving a gamma function bound for the summation of an infinite series, so that he can apply the Mellin transform, a technique he is rather famous for. Almost none of this is relevant to understanding the peculiarities of big-O notation, however; most of the chapter is strictly irrelevant if the goal is just to understand the specific topic at hand, or even merely to support the idea that discussion of sorting algorithms usually measures them by number of comparisons. 5.3 is probably the most relevant, but here he explicitly discusses the flaws of using comparisons as a basis for performance analysis (indeed, that section starts by noting that some of the sorting techniques he covers require no comparisons at all, and so the minimum number of comparisons is zero). Of course, by the time we get to section 5.4, the criteria necessarily changes, since discussion of external sorting hinges on the premise that the data to be sorted is so large that it does not fit into main memory, where direct comparison is not applicable. So I ask again, could you be more precise about what, exactly, you were referring to in the chapter? As far as Knuth and TAOCP is concerned, the most useful material supporting your statement in this context is covered in the first 5 pages. >> Further, "See Knuth chapter 5" is an imperative statement, not a >> statement of fact about something you had done. >> >> My point is that, if your goal is to a establish shared working >> vocabulary with Waldek, such a directive is, unfortunately, not >> likely to be particularly useful towards that goal. > >My goal was only to support my statement "it is customary in >discussion of sorting algorithms to use the metric of number of >comparisons done [...]". No goal other than that. But that citation does not support that statement in a meaningful way. Indeed, it contradicts it in a number of places. >>>> "See chapter 5" is thus not useful as a reference, and rather >>>> comes across as an admonishment. >>> >>> No admonishment was intented. I mentioned it only as a supporting >>> work for my previous statement. >> >> My point is that the statement is too vague. A more useful >> citation would be to a section, or perhaps a page number, >> edition, and printing, or perhaps a direct quotation. > >I'm sorry you thought the statement was too vague. I thought it >was clear enough when I wrote it. > >> Absent a more refined citation, the reference to Knuth comes >> across as more of an appeal to authority than something that is >> actually meant to illuminate the discussion. > >The reference to Knuth was only to support my earlier statement. >I had thought that was evident. Again, your reference to Knuth is too broad to shed light on any implied meaning. It is only negligibly more precise than saying, "see the literature." >> I trust you that that was Not your intent, however. >> >> I do think this is actually useful, even in the context of >> comp.lang.c; a lot of people posting here seem to have forgotten >> many of the finer points of analyzing the characteristics of the >> code that is frequently under discussion, and understanding how >> to apply such to C code is an important skill. > >In any discussion it's important to keep in mind which details are >essential to the discussion and which ones are better left out. It >was my judgment that in the context of the post(s) I was responding >to that the number of comparisons, as a function of the number of >records to be sorted, was a key part of the discussion, but that >more detailed analysis was unnecessary. Other people are free to >have their own views on that question. However, for what I was >trying to get across, I still think the level of detail I settled >on was an appropriate choice for what I was hoping to convey. This actually reinforces my point. Knuth's writing covers so much material, so broadly, that the details obscure the point you were evidently trying to make. The references I proposed do a much better job of supporting your statement, IMHO, and are far more useful and accessible to actual working programmers writing C programs. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-03-20 14:01 +0200 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260320140110.00006b84@yahoo.com> |
| In reply to | #397095 |
On Thu, 19 Mar 2026 23:53:35 +0000
Bart <bc@freeuk.com> wrote:
> On 19/03/2026 19:40, Michael S wrote:
> > On Thu, 19 Mar 2026 18:33:13 +0000
> > Bart <bc@freeuk.com> wrote:
> >
> >> On 19/03/2026 15:29, Michael S wrote:
> >>> On Thu, 19 Mar 2026 14:49:16 +0000
> >>> Bart <bc@freeuk.com> wrote:
> >>>
> >>>> On 19/03/2026 09:19, Michael S wrote:
> >>>>> On Wed, 18 Mar 2026 11:20:03 +0100
> >>>>> David Brown <david.brown@hesbynett.no> wrote:
> >>>>
> >>>>
> >>>> Normally however (and again in scripting code) I'd use my
> >>>> built-in sort() based on quicksort, which is nearly 1000 times
> >>>> faster than bubble-sort for my test (sort 20K random strings),
> >>>> and some 300x faster than your routines. It's not O(n-squared)
> >>>> either.
> >>>
> >>> For lexicographic sort of 20K random strings, plain quicksort is
> >>> probably quite sub-optimal.
> >>> If performance is important, I'd consider combined method: first
> >>> pre-sort by 3-char or 4-char prefix with Radix sort ('by LS
> >>> character first' variation of algorithm), then use quicksprt to
> >>> sort sections with the same prefix. For string taken from the real
> >>> world it will not work as well as for artificial random strings,
> >>> but should still significantly outperform plain quicksort.
> >>>
> >>
> >> What do you think the slow-down would be? I set up another test,
> >> sorting 1M random strings each exactly 16 characters long.
> >>
> >> This is how long it took to sort via various means:
> >>
> >> WSL shell 'sort': 2.3/3.5 seconds (real/user, from/to a file)
> >> Windows 'sort': 4.2 seconds (from/to a file)
> >> C's qsort: 0.5 seconds (gcc; initialised
> >> char*[]/inplace) 0.6 seconds (tcc)
> >> My script lang: 2.3/2.8 seconds (sort only/all, file to
> >> in-memory)
> >>
> >> (That last timing is somewhat remarkable given (1) that the sort
> >> routine itself runs as interpreted, dynamic bytecode; (2) each
> >> string compare involves calling C's 'strcmp' /after/ converting
> >> args to ensure strings are zero-terminated.)
> >>
> >> So how much faster ought it to be?
> >>
> >
> >
> > I don't understand the question. What answer could there possibly be
> > except for "There are no limits to perfection!" ?
>
> You said that plain quicksort (I guess that is what I used) is likely
> 'sub-optimal' and that your complex approach will 'significantly
> outperform' it.
>
> So I'm just asking 'by how much'?
How could I possibly know?
It depends on dataset (size and distribution) and on specifics of your
compute engine (CPU core, caches, memory speed).
The only thing I can tell that for the range of N you are talking
about, i.e. 20k to 1M, the speed up of the sort part would be
significant. I am sure about 2x, but not about 10x. For the rest, only
measurements can tell.
Of course, if your file system is slow, e.g. because of antivirus or
because of ancient storage hardware, then the speedup of the whole
job of reading-sorting-writing would be lost in the noise.
But you know that already.
Ifyou want data set to compare your results with other people, then I
propose to use bible.txt from Canterbury Corpus:
https://corpus.canterbury.ac.nz/resources/large.zip
Or, if you found it too short, here is the text that considered the
longest novel ever written:
https://standardebooks.org/ebooks/marcel-proust/in-search-of-lost-time/c-k-scott-moncrieff/text/single-page
It is rather short, too, only 100K lines, but I can not think about
anything longer and not artificial.
>
> My figures suggested it was fast enough. However I don't know what
> kind of sort routines are used in that table except for mine, which
> is not native code.
>
> So I ported my sort to C, but the figures are pretty much the same as
> C's qsort(): 0.5 seconds for both tcc/gcc, even though it uses
> dedicated compare code.
>
> That routine is given below (not my algorithm; I adapted it long ago).
>
> That it is 5-8 times as fast as shell methods of sorting (even
> allowing for those to load and write files) seems good enough for me.
>
> However, in my programs, I would look askance at anything that
> required such a sorting step anyway. It's something I try and avoid.
>
>
> -----------------------
> void isort(char** data, int ll, int rr) {
> char* temp;
> int i = ll, j = rr;
> char* pivot = data[(ll + rr) / 2];
>
> do {
> while (strcmp(pivot, data[i]) > 0 && i < rr) ++i;
> while (strcmp(pivot, data[j]) < 0 && j > ll) --j;
>
> if (i <= j) {
> temp = data[i]; data[i] = data[j]; data[j] = temp;
> ++i;
> --j;
> }
> } while (i <= j);
>
> if (ll < j) isort(data, ll, j);
> if (i < rr) isort(data, i, rr);
> }
>
> //For a char* array A of N elements, call as 'isort(A, 0, n-1)'.
>
Looks o.k. speed wise.
It is not ideomatic C, probably a literal translation from Fortran or
Pascal, but with modern compilers it is not supposed to make a lot of
difference. With tcc, it could pay of to re-write in more ideomatic
manner
In professional practice people normally do two or three modifications
to the basic algorithm:
1. pivot is selected as median of 3 {data[0], data[n/2], data[n-1])
2. after split, shorter section is sorted before longer section
3. short sections, say, under 10 entries, are sorted by straight
insertion algorithm
(1) make worst case O(N*N) behavior extremely unlikely
(2) assures that even when worst case happens the depth of recursion do
not exceed log2(N). Which can be important on systems with small
default stack size.
(3) is believed to provide some speed up. The belief not always found
true, but it persists.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-06 13:48 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <868qazzugr.fsf@linuxsc.com> |
| In reply to | #397110 |
Michael S <already5chosen@yahoo.com> writes:
[discussion of sorting code]
>> -----------------------
>> void isort(char** data, int ll, int rr) {
>> char* temp;
>> int i = ll, j = rr;
>> char* pivot = data[(ll + rr) / 2];
>>
>> do {
>> while (strcmp(pivot, data[i]) > 0 && i < rr) ++i;
>> while (strcmp(pivot, data[j]) < 0 && j > ll) --j;
>>
>> if (i <= j) {
>> temp = data[i]; data[i] = data[j]; data[j] = temp;
>> ++i;
>> --j;
>> }
>> } while (i <= j);
>>
>> if (ll < j) isort(data, ll, j);
>> if (i < rr) isort(data, i, rr);
>> }
>>
>> //For a char* array A of N elements, call as 'isort(A, 0, n-1)'.
>
> Looks o.k. speed wise.
> It is not ideomatic C,
What about the code prompts you to say it is not idiomatic C?
Is it because there is a line with multiple statements on it,
or is there something else?
Personally I would not call this code non-idiomatic, with
having three statements on one line a minor style exception.
Also I think Bart should be applauded for posting code that
AFAICT falls completely within the confines of ISO C, and
even looks fairly natural, style-wise.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-07 01:58 +0300 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <20260407015823.00005a2f@yahoo.com> |
| In reply to | #397391 |
On Mon, 06 Apr 2026 13:48:04 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> [discussion of sorting code]
>
> >> -----------------------
> >> void isort(char** data, int ll, int rr) {
> >> char* temp;
> >> int i = ll, j = rr;
> >> char* pivot = data[(ll + rr) / 2];
> >>
> >> do {
> >> while (strcmp(pivot, data[i]) > 0 && i < rr) ++i;
> >> while (strcmp(pivot, data[j]) < 0 && j > ll) --j;
> >>
> >> if (i <= j) {
> >> temp = data[i]; data[i] = data[j]; data[j] = temp;
> >> ++i;
> >> --j;
> >> }
> >> } while (i <= j);
> >>
> >> if (ll < j) isort(data, ll, j);
> >> if (i < rr) isort(data, i, rr);
> >> }
> >>
> >> //For a char* array A of N elements, call as 'isort(A, 0, n-1)'.
> >
> > Looks o.k. speed wise.
> > It is not ideomatic C,
>
> What about the code prompts you to say it is not idiomatic C?
> Is it because there is a line with multiple statements on it,
> or is there something else?
>
Something else.
Here is a mechanical translation of Bart's code to what I consider more
idiomatic C. Pay attention, the translation was mechanical, I didn't
check if original logic is 100% correct and whether it is possible to
omit some checks.
void isort(char** data, int len) {
if (len > 1) {
char** i = data, j = &data[len-1];
char* pivot = data[(len-1) / 2];
do {
while (strcmp(pivot, *i) > 0 && i < &data[len-1]) ++i;
while (strcmp(pivot, *j) < 0 && j > data) --j;
if (i <= j) {
char* temp = *i; *i = *j; *j = temp;
++i;
--j;
}
} while (i <= j);
if (j > data) isort(data, j+1-data);
if (i < &data[len-1]) isort(i, &data[len]-i);
}
}
Whether i and j are pointers or integers is less important.
But passing into call two indices instead of one and the fact that the
second index points into last element of araay instead of the next
place after last element is certainly non-idiomatic.
> Personally I would not call this code non-idiomatic, with
> having three statements on one line a minor style exception.
>
> Also I think Bart should be applauded for posting code that
> AFAICT falls completely within the confines of ISO C, and
> even looks fairly natural, style-wise.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2026-04-07 01:02 +0100 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10r1hi2$2foc7$1@dont-email.me> |
| In reply to | #397397 |
On 06/04/2026 23:58, Michael S wrote:
> On Mon, 06 Apr 2026 13:48:04 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>> [discussion of sorting code]
>>
>>>> -----------------------
>>>> void isort(char** data, int ll, int rr) {
>>>> char* temp;
>>>> int i = ll, j = rr;
>>>> char* pivot = data[(ll + rr) / 2];
>>>>
>>>> do {
>>>> while (strcmp(pivot, data[i]) > 0 && i < rr) ++i;
>>>> while (strcmp(pivot, data[j]) < 0 && j > ll) --j;
>>>>
>>>> if (i <= j) {
>>>> temp = data[i]; data[i] = data[j]; data[j] = temp;
>>>> ++i;
>>>> --j;
>>>> }
>>>> } while (i <= j);
>>>>
>>>> if (ll < j) isort(data, ll, j);
>>>> if (i < rr) isort(data, i, rr);
>>>> }
>>>>
>>>> //For a char* array A of N elements, call as 'isort(A, 0, n-1)'.
>>>
>>> Looks o.k. speed wise.
>>> It is not ideomatic C,
>>
>> What about the code prompts you to say it is not idiomatic C?
>> Is it because there is a line with multiple statements on it,
>> or is there something else?
>>
>
> Something else.
> Here is a mechanical translation of Bart's code to what I consider more
> idiomatic C. Pay attention, the translation was mechanical, I didn't
> check if original logic is 100% correct and whether it is possible to
> omit some checks.
>
> void isort(char** data, int len) {
> if (len > 1) {
> char** i = data, j = &data[len-1];
> char* pivot = data[(len-1) / 2];
> do {
> while (strcmp(pivot, *i) > 0 && i < &data[len-1]) ++i;
> while (strcmp(pivot, *j) < 0 && j > data) --j;
> if (i <= j) {
> char* temp = *i; *i = *j; *j = temp;
> ++i;
> --j;
> }
> } while (i <= j);
> if (j > data) isort(data, j+1-data);
> if (i < &data[len-1]) isort(i, &data[len]-i);
> }
> }
>
> Whether i and j are pointers or integers is less important.
> But passing into call two indices instead of one and the fact that the
> second index points into last element of araay instead of the next
> place after last element is certainly non-idiomatic.
It can be idiomatic for a Quicksort API. I've just browsed loads of
examples on RosettaCode, and Left/Right arguments are common, even when
arrays contain their own dimensions so allowing slices to be passed.
Regarding the upper bound not being one past the end, both are intended
to refer to actual elements.
I also saw some examples like this Python:
def quicksort(array):
_quicksort(array, 0, len(array) - 1)
def _quicksort(array, start, stop): ...
Python is zero-based like C, but here the 'stop' index is still that of
the last element, not one past.
I think your idea of idiomatic C is to have something that is harder to
understand and less readable. I acknowledge that a lot of C is like
that, but it doesn't need to be.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-07 08:01 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86bjfuyftu.fsf@linuxsc.com> |
| In reply to | #397397 |
Michael S <already5chosen@yahoo.com> writes:
> On Mon, 06 Apr 2026 13:48:04 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>> [discussion of sorting code]
>>
>>>> -----------------------
>>>> void isort(char** data, int ll, int rr) {
>>>> char* temp;
>>>> int i = ll, j = rr;
>>>> char* pivot = data[(ll + rr) / 2];
>>>>
>>>> do {
>>>> while (strcmp(pivot, data[i]) > 0 && i < rr) ++i;
>>>> while (strcmp(pivot, data[j]) < 0 && j > ll) --j;
>>>>
>>>> if (i <= j) {
>>>> temp = data[i]; data[i] = data[j]; data[j] = temp;
>>>> ++i;
>>>> --j;
>>>> }
>>>> } while (i <= j);
>>>>
>>>> if (ll < j) isort(data, ll, j);
>>>> if (i < rr) isort(data, i, rr);
>>>> }
>>>>
>>>> //For a char* array A of N elements, call as 'isort(A, 0, n-1)'.
>>>
>>> Looks o.k. speed wise.
>>> It is not ideomatic C,
>>
>> What about the code prompts you to say it is not idiomatic C?
>> Is it because there is a line with multiple statements on it,
>> or is there something else?
>
> Something else.
> Here is a mechanical translation of Bart's code to what I consider more
> idiomatic C. Pay attention, the translation was mechanical, I didn't
> check if original logic is 100% correct and whether it is possible to
> omit some checks.
>
> void isort(char** data, int len) {
> if (len > 1) {
> char** i = data, j = &data[len-1];
> char* pivot = data[(len-1) / 2];
> do {
> while (strcmp(pivot, *i) > 0 && i < &data[len-1]) ++i;
> while (strcmp(pivot, *j) < 0 && j > data) --j;
> if (i <= j) {
> char* temp = *i; *i = *j; *j = temp;
> ++i;
> --j;
> }
> } while (i <= j);
> if (j > data) isort(data, j+1-data);
> if (i < &data[len-1]) isort(i, &data[len]-i);
> }
> }
>
> Whether i and j are pointers or integers is less important.
> But passing into call two indices instead of one and the fact that the
> second index points into last element of araay instead of the next
> place after last element is certainly non-idiomatic.
I agree that using one past the last item is more common. I
myself wouldn't call using at the last item non-idiomatic,
but I understand your point.
As for whether the number of index/pointer arguments is one
or two, that's an internal design decision. Depending on
other factors either choice might be preferable; I have
used both in the past, even just in this last exercise of
trying out different sorting algorithms. So I have to
object to calling either choice non-idiomatic.
[toc] | [prev] | [next] | [standalone]
| From | antispam@fricas.org (Waldek Hebisch) |
|---|---|
| Date | 2026-03-19 23:21 +0000 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <10pi0e5$3hn36$1@paganini.bofh.team> |
| In reply to | #397090 |
Bart <bc@freeuk.com> wrote:
> On 19/03/2026 15:29, Michael S wrote:
>> On Thu, 19 Mar 2026 14:49:16 +0000
>> Bart <bc@freeuk.com> wrote:
>>
>>> On 19/03/2026 09:19, Michael S wrote:
>>>> On Wed, 18 Mar 2026 11:20:03 +0100
>>>> David Brown <david.brown@hesbynett.no> wrote:
>>>
>>>
>>> Normally however (and again in scripting code) I'd use my built-in
>>> sort() based on quicksort, which is nearly 1000 times faster than
>>> bubble-sort for my test (sort 20K random strings), and some 300x
>>> faster than your routines. It's not O(n-squared) either.
>>>
>>
>> For lexicographic sort of 20K random strings, plain quicksort is
>> probably quite sub-optimal.
>> If performance is important, I'd consider combined method: first
>> pre-sort by 3-char or 4-char prefix with Radix sort ('by LS character
>> first' variation of algorithm), then use quicksprt to sort sections
>> with the same prefix. For string taken from the real world it will not
>> work as well as for artificial random strings, but should still
>> significantly outperform plain quicksort.
>>
>
> What do you think the slow-down would be? I set up another test, sorting
> 1M random strings each exactly 16 characters long.
>
> This is how long it took to sort via various means:
>
> WSL shell 'sort': 2.3/3.5 seconds (real/user, from/to a file)
> Windows 'sort': 4.2 seconds (from/to a file)
> C's qsort: 0.5 seconds (gcc; initialised char*[]/inplace)
> 0.6 seconds (tcc)
> My script lang: 2.3/2.8 seconds (sort only/all, file to in-memory)
>
> (That last timing is somewhat remarkable given (1) that the sort routine
> itself runs as interpreted, dynamic bytecode; (2) each string compare
> involves calling C's 'strcmp' /after/ converting args to ensure strings
> are zero-terminated.)
>
> So how much faster ought it to be?
quicksort needs 20-30 passes, on several passes you are likely to get
cache miss per access to string. Assuming nominally 100 clocks
per cache miss, miss in each pass and 25 passes we get 2.5e9 clocks
which for 2.4GHz machine would give 1.2s. Hardware may be able
to handle more than one miss in parallel, for quicksort it is
tricky to get more than 2 misses in parallel. 0.5s means that your
hardware is doing reasonably good job Radix sort should be able to
do work in 10-15 passes with similar cost per pass, so there is
potential for speeding this 2 times. Single pass of radix sort will
give modest speedup.
AFAICS more speedup is possible by working directly on strings,
that is treating each string as 16 byte memory area and comparing
them with 8 byte operations. In such case single pass of quicksort
should take 2-3 ms so the is possibility of 5 time speedup.
but working directly with strings gets more complicated when
strings are of variable size. As a compromise one could pad
each string to multiple of 8 bytes, work with pointers but
also copy strings. That will ensure sequential access to
string data.
There is a tradeoff: copying means more instructions, but it
allows sequential access in the next pass, so means less
cache misses. Copying only pointers means more cache misses.
If strings are long one could do some number of passes working
on copy of prefix and orignal pointer, once this is sorted
one can work in subsequent characters. That way one can
reduce amount of data that needs copying (but somewhat
decrease locality).
Knuth claimed that tape sort was of comparable cost to copy:
that is even if you had perfect knowledge where each piece
of data should go it would not help much: you would need to
do something like sort to ensure sequential access.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-06 18:37 -0700 |
| Subject | Re: sorting Was: Isn't that beauty ? (no it's not) |
| Message-ID | <86v7e3y2hg.fsf@linuxsc.com> |
| In reply to | #397088 |
Michael S <already5chosen@yahoo.com> writes:
> On Thu, 19 Mar 2026 14:49:16 +0000
> Bart <bc@freeuk.com> wrote:
>
>> On 19/03/2026 09:19, Michael S wrote:
>>
>>> On Wed, 18 Mar 2026 11:20:03 +0100
>>> David Brown <david.brown@hesbynett.no> wrote:
>>
>> Normally however (and again in scripting code) I'd use my built-in
>> sort() based on quicksort, which is nearly 1000 times faster than
>> bubble-sort for my test (sort 20K random strings), and some 300x
>> faster than your routines. It's not O(n-squared) either.
>
> For lexicographic sort of 20K random strings, plain quicksort is
> probably quite sub-optimal.
> If performance is important, I'd consider combined method: first
> pre-sort by 3-char or 4-char prefix with Radix sort ('by LS character
> first' variation of algorithm), then use quicksprt to sort sections
> with the same prefix. For string taken from the real world it will not
> work as well as for artificial random strings, but should still
> significantly outperform plain quicksort.
Put the strings in a hash table. If a string has been seen
before nothing more needs to be done. Any string not seen
before to be inserted into a balanced tree (with no further
tests for equality needed). The balanced tree can be used as
a basis to associate an integer with each string, where the
associated integers have the same sort order as the strings.
The only string comparisons needed are for building the
hash table (which for the most part will have no misses),
and for building the balanced tree, which is good because
most of the comparisons are with values that are far away,
lexicographically, from the string being inserted, and so
not many character comparisons are needed before a decision
is made about which way to go in the tree.
[toc] | [prev] | [next] | [standalone]
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Date | 2026-03-20 04:33 +0100 |
| Subject | Re: Isn't that beauty ? (no it's not) |
| Message-ID | <10pif5m$17mc2$4@dont-email.me> |
| In reply to | #397077 |
On 2026-03-19 10:19, Michael S wrote: > On Wed, 18 Mar 2026 11:20:03 +0100 > David Brown <david.brown@hesbynett.no> wrote: >> >> Bogosort is O(n * n!) on average - keep rearranging the elements at >> random, then check if they are sorted. (The worst case is only >> bounded complexity if your random generator is pseduo-random rather >> than truly random.) > > I didn't mean something intentionally crippled. > I remember seeing examples of worse than O(n**2) algorithms that at > first glance look reasonable. I don't remember details. Then it's best to abandon imagined examples. (Or search for it and then report about them so that we have something substantial to talk about.) >> [...] > > The language is 'C'. > Here are implementations of Straight Insertion and Straight Select. > Show me implementation of Bubble sort that is not at least a little > more complicated. I don't know about you, but Bubblesort is trivial, and the other two O(N^2) methods you mention are close to trivial. Certainly they play in the same "league". Compare these algorithms to the other sophisticated algorithms whose principles usually cannot be *obviously* understood (e.g. Quicksort, Shellsort, even Heapsort. (There's a point (but negligible) if some other poster previously said that it's easier for him to program Bubblesort than something even slightly more sophisticated.) Of course you can tweak any algorithm to make it better. But if you're starting with a bad choice of an algorithm you won't fix the inherent issues. > Remember that it has to be "real" bubble sort, not a simplified bubble > sort that does unnecessary work by starting each time from the > beginning. [...] (There's Bubblesort. There's not "real" Bubblesort. Such phrases neither explain anything nor are they helpful for discussions.) Janis > [...]
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-03-20 14:24 +0200 |
| Subject | Re: Isn't that beauty ? (no it's not) |
| Message-ID | <20260320142421.00002d75@yahoo.com> |
| In reply to | #397101 |
On Fri, 20 Mar 2026 04:33:10 +0100 Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote: > On 2026-03-19 10:19, Michael S wrote: > > On Wed, 18 Mar 2026 11:20:03 +0100 > > David Brown <david.brown@hesbynett.no> wrote: > >> > >> Bogosort is O(n * n!) on average - keep rearranging the elements at > >> random, then check if they are sorted. (The worst case is only > >> bounded complexity if your random generator is pseduo-random rather > >> than truly random.) > > > > I didn't mean something intentionally crippled. > > I remember seeing examples of worse than O(n**2) algorithms that at > > first glance look reasonable. I don't remember details. > > Then it's best to abandon imagined examples. (Or search for it > and then report about them so that we have something substantial > to talk about.) > > >> [...] > > > > The language is 'C'. > > Here are implementations of Straight Insertion and Straight Select. > > Show me implementation of Bubble sort that is not at least a little > > more complicated. > > I don't know about you, but Bubblesort is trivial, and the other > two O(N^2) methods you mention are close to trivial. Certainly > they play in the same "league". Compare these algorithms to the > other sophisticated algorithms whose principles usually cannot be > *obviously* understood (e.g. Quicksort, Shellsort, even Heapsort. > > (There's a point (but negligible) if some other poster previously > said that it's easier for him to program Bubblesort than something > even slightly more sophisticated.) > > Of course you can tweak any algorithm to make it better. But if > you're starting with a bad choice of an algorithm you won't fix > the inherent issues. > > > Remember that it has to be "real" bubble sort, not a simplified > > bubble sort that does unnecessary work by starting each time from > > the beginning. [...] > > (There's Bubblesort. There's not "real" Bubblesort. Such phrases > neither explain anything nor are they helpful for discussions.) > > Janis > > > [...] > The challenge was issued for David Brown and for Bart. I never expected that you will give constructive reply. Thank you for confirming my expectations.
[toc] | [prev] | [next] | [standalone]
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Date | 2026-03-22 05:06 +0100 |
| Subject | Re: Isn't that beauty ? (no it's not) |
| Message-ID | <10pnpsm$301pg$4@dont-email.me> |
| In reply to | #397114 |
On 2026-03-20 13:24, Michael S wrote: > > The challenge was issued for David Brown and for Bart. If you think that Usenet is for private communication you've a fundamental misconception about that. > I never expected that you will give constructive reply. Your perception may be severely impaired, but I don't care much. I don't know about you, but I find requests for clarification a sensible demand. You didn't answer to that but preferred keeping the discussion muddy with your phrases; the context was you saying: >> Remember that it has to be "real" bubble sort, not a simplified bubble >> sort that does unnecessary work by starting each time from the >> beginning. [...] And I noted: > (There's Bubblesort. There's not "real" Bubblesort. Such phrases > neither explain anything nor are they helpful for discussions.) You could have clarified that fuzzy statement instead of rambling. > Thank you for confirming my expectations. I hope you feel good in your mental bubble.[*] Janis [*] No pun with Bubblesort intended.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-03-22 09:30 +0200 |
| Subject | Re: Isn't that beauty ? (no it's not) |
| Message-ID | <20260322093016.00006b06@yahoo.com> |
| In reply to | #397136 |
On Sun, 22 Mar 2026 05:06:46 +0100 Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote: > On 2026-03-20 13:24, Michael S wrote: > > > > The challenge was issued for David Brown and for Bart. > > If you think that Usenet is for private communication you've a > fundamental misconception about that. > > > I never expected that you will give constructive reply. > > Your perception may be severely impaired, but I don't care much. > Probably I had to be more polite. But you were not involved in this particular argument where Bart and David were claiming that good implementation of bublesort is of the same complexity of coding as Staright Insertion and Straigh Select sorts and I was claiming that the lattter two are simpler, even if not by much. So, even if you provide your variant of bublesort coded in 'C' it would not be conclusive, because you are not a party interstead in the proof of his point. > I don't know about you, but I find requests for clarification a > sensible demand. You didn't answer to that but preferred keeping > the discussion muddy with your phrases; the context was you saying: > > >> Remember that it has to be "real" bubble sort, not a simplified > >> bubble sort that does unnecessary work by starting each time from > >> the beginning. [...] > > And I noted: > > > (There's Bubblesort. There's not "real" Bubblesort. Such phrases > > neither explain anything nor are they helpful for discussions.) > > You could have clarified that fuzzy statement instead of rambling. > > > Thank you for confirming my expectations. > > I hope you feel good in your mental bubble.[*] > > Janis > > [*] No pun with Bubblesort intended. >
[toc] | [prev] | [next] | [standalone]
Page 9 of 12 — ← Prev page 1 … 7 8 [9] 10 11 12 Next page →
Back to top | Article view | comp.lang.c
csiph-web