Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Program to sort three integers |
| Date | 2015-11-06 22:52 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87611eviz5.fsf@bsb.me.uk> (permalink) |
| References | <8dcd1ed2-2734-4cff-b013-d713a33100ed@googlegroups.com> <n1ilap$85f$1@dont-email.me> <lnoaf63oo6.fsf@kst-u.example.com> <mstorkamp-6548C9.16045906112015@88-209-239-213.giganet.hu> |
Mark Storkamp <mstorkamp@yahoo.com> writes:
> In article <lnoaf63oo6.fsf@kst-u.example.com>,
> Keith Thompson <kst-u@mib.org> wrote:
<snip>
>> #include <stdio.h>
>>
>> void sort2(int *x, int *y) {
>> if (*x > *y) {
>> const int old_x = *x;
>> *x = *y;
>> *y = old_x;
>> }
>> }
>>
>> void sort3(int *x, int *y, int *z) {
>> sort2(x, y);
>> sort2(y, z);
>> sort2(x, y);
>> }
<snip>
> It looks like it scales fairly nicely.
>
> void sort4(int *x, int *y, int *z, int *t) {
> sort3(x, y, z);
> sort3(y, z, t);
> sort3(x, y, z);
> }
>
> void sort5(int *x, int *y, int *z, int *t, int *u) {
> sort4(x, y, z, t);
> sort4(y, z, t, u);
> sort4(x, y ,z, t);
> }
>
> etc.
These don't scale well in terms of comparisons done. sort2 and sort3
are optimal in that they take 1 and 3 comparisons respectively. But
sorting 4 elements can be done with only 5 comparisons where sort4 uses
9. sort4 uses 27 where the optimal number is only 7.
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-06 08:20 -0800
Re: Program to sort three integers Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-06 11:32 -0500
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 00:20 -0800
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-07 11:04 +0000
Re: Program to sort three integers "Osmium" <r124c4u102@comcast.net> - 2015-11-06 10:34 -0600
Re: Program to sort three integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-11-06 08:37 -0800
Re: Program to sort three integers supercat@casperkitty.com - 2015-11-06 10:36 -0800
Re: Program to sort three integers Richard Heathfield <rjh@cpax.org.uk> - 2015-11-06 19:17 +0000
Re: Program to sort three integers supercat@casperkitty.com - 2015-11-06 11:30 -0800
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 01:01 -0800
Re: Program to sort three integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-11-06 11:48 -0800
Re: Program to sort three integers David Brown <david.brown@hesbynett.no> - 2015-11-06 23:15 +0100
Re: Program to sort three integers "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-11-06 14:39 -0800
Re: Program to sort three integers Keith Thompson <kst-u@mib.org> - 2015-11-06 15:57 -0800
Re: Program to sort three integers Nick Bowler <nbowler@draconx.ca> - 2015-11-06 22:33 +0000
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-06 16:39 +0000
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 00:22 -0800
Re: Program to sort three integers Richard Heathfield <rjh@cpax.org.uk> - 2015-11-06 16:45 +0000
Re: Program to sort three integers "Bill Davy" <Bill@SynectixLtd.com> - 2015-11-06 18:30 +0000
Re: Program to sort three integers Keith Thompson <kst-u@mib.org> - 2015-11-06 11:36 -0800
Re: Program to sort three integers Bartc <bc@freeuk.com> - 2015-11-06 19:50 +0000
Re: Program to sort three integers Keith Thompson <kst-u@mib.org> - 2015-11-06 12:52 -0800
Re: Program to sort three integers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-09 13:36 +0000
Re: Program to sort three integers David Brown <david.brown@hesbynett.no> - 2015-11-09 15:41 +0100
Re: Program to sort three integers raltbos@xs4all.nl (Richard Bos) - 2015-11-10 16:56 +0000
Re: Program to sort three integers Keith Thompson <kst-u@mib.org> - 2015-11-10 09:11 -0800
Re: Program to sort three integers supercat@casperkitty.com - 2015-11-10 09:15 -0800
Re: Program to sort three integers Les Cargill <lcargill99@comcast.com> - 2015-11-10 19:37 -0600
Re: Program to sort three integers asetofsymbols@gmail.com - 2015-11-06 11:52 -0800
Re: Program to sort three integers Bartc <bc@freeuk.com> - 2015-11-06 20:01 +0000
Re: Program to sort three integers asetofsymbols@gmail.com - 2015-11-06 12:21 -0800
Re: Program to sort three integers "Osmium" <r124c4u102@comcast.net> - 2015-11-06 14:23 -0600
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-06 20:58 +0000
Re: Program to sort three integers Mark Storkamp <mstorkamp@yahoo.com> - 2015-11-06 16:04 -0600
Re: Program to sort three integers Mark Storkamp <mstorkamp@yahoo.com> - 2015-11-06 16:08 -0600
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-06 22:49 +0000
Re: Program to sort three integers Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-10 16:04 -0800
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-11 21:51 +0000
Re: Program to sort three integers bartekltg <bartekltg@gmail.com> - 2015-11-11 23:50 +0100
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-06 22:52 +0000
Re: Program to sort three integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-07 01:17 +0000
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 01:24 -0800
Re: Program to sort three integers Chad <cdalten@gmail.com> - 2015-11-07 02:04 -0800
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 00:57 -0800
Re: Program to sort three integers Barry Schwarz <schwarzb@dqel.com> - 2015-11-06 10:14 -0800
Re: Program to sort three integers Richard Heathfield <rjh@cpax.org.uk> - 2015-11-06 18:27 +0000
Re: Program to sort three integers Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-06 11:22 -0800
Re: Program to sort three integers Alla _ <modelling.data@gmail.com> - 2015-11-07 01:15 -0800
Re: Program to sort three integers Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-07 00:57 -0800
Re: Program to sort three integers bartekltg <bartekltg@gmail.com> - 2015-11-10 02:07 +0100
csiph-web