Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397510
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Isn't that beauty ? (no it's not) |
| Date | 2026-04-12 11:16 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86bjfo82nh.fsf@linuxsc.com> (permalink) |
| References | (16 earlier) <10pcvr2$3ednq$2@dont-email.me> <20260318112151.000021dc@yahoo.com> <10pdu8k$3o60c$1@dont-email.me> <20260319111959.0000447c@yahoo.com> <86fr57xhf2.fsf@linuxsc.com> |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
[...]
After my previous posting I got curious about how different sorting
algorithms behave for "nearly sorted" inputs. I decided to run some
trials for some of the sorting functions given in my last posting.
Here are the results:
Average number of compares for sorting 100 elements, with one
element out of place:
insertion sort 132.647
gnome sort 166.293
ping pong sort 180.177
knuth bubble sort 956.500
Average number of compares for sorting 100 elements, with two
elements out of place:
insertion sort 166.126
gnome sort 233.253
ping pong sort 234.163
knuth bubble sort 1566.487
My conclusion, based on the above, is that bubble sort has nothing
to recommend it as a practical sorting algorithm, even considering
the refinement of early pruning (called the "knuth bubble sort" in
the list above). The gnome sort is both simpler and better in terms
of performance.
Incidentally, some years ago I devised a variation of gnome sort,
which I call "leaping gnome sort". A leaping gnome sort is like
gnome sort when going right to left, that is, when the elements
being looked at are out of order, swap them and move one place to
the left. When no swap is needed, the gnome "leaps" to the last
place a rightward shift was initiated. In terms of code, leaping
gnome sort can be written as follows:
void
leaping_gnome_sort( unsigned n, Element a[n] ){
for(
unsigned i = 1, j = 2;
i < n;
i = follows(i-1,i,a) ? swap(i-1,i,a), i>1 ?i-1 :j++ : j++
){}
}
The "leaping" behavior is evident whenever the current location 'i'
gets the value 'j++' rather than 'i-1'.
Of course this algorithm could be written using a while() loop
rather than a for() loop:
void
leaping_gnome_sort( unsigned n, Element a[n] ){
unsigned i = 1, j = 2;
while( i < n ){
if( !follows(i-1,i,a) ) i = j++;
else {
swap(i-1,i,a);
i = i > 1 ? i-1 : j++;
}
}
}
In either case it's nice having only a single loop structure rather
than an outer loop and a second, nested loop.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 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) 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
csiph-web