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-11 21:51 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <876118kxwt.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <lnoaf63oo6.fsf@kst-u.example.com> <mstorkamp-6548C9.16045906112015@88-209-239-213.giganet.hu> <mstorkamp-B3F014.16085906112015@88-209-239-213.giganet.hu> <87bnb6vj4z.fsf@bsb.me.uk> <kfnd1vhfljo.fsf@x-alumni2.alumni.caltech.edu> |
Tim Rentsch <txr@alumni.caltech.edu> writes:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Mark Storkamp <mstorkamp@yahoo.com> writes:
>> <snip>
>>> Even simpler,
>>> void sort4(int *x, int *y, int *z, int *t) {
>>> sort3(x, y, z);
>>> sort2(z, t);
>>> sort3(x, y, z);
>>> }
>>>
>>> void sort5(int *x, int *y, int *z, int *t, int *u) {
>>> sort4(x, y, z, t);
>>> sort2(t, u);
>>> sort4(x, y ,z, t);
>>
>> Sadly, no. These fail in some cases.
>
> Oh? They look like they work to me. Can you give an
> example?
No, I can't! My test must have been faulty. I don't have the test code
anymore but I can't re-create the problem.
To add a positive contribution, you can improve on the number of
comparisons by using another symmetry:
sort3(x, y, z);
sort2(z, t);
sort2(y, z);
sort2(x, y);
sort4(x, y, z, t);
sort2(t, u);
sort2(z, t);
sort2(y, z);
sort2(x, y);
in effect simply putting the extra element in place with a "bubble".
Less pretty, perhaps, but fewer comparisons. And you can get fewer
still (and fewer moves) if sort2 reports true/false when it swaps or
doesn't:
sort3(x, y, z);
sort2(z, t) && sort2(y, z) && sort2(x, y);
sort4(x, y, z, t);
sort2(t, u) && sort2(z, t) && sort2(y, z) && sort2(x, y);
--
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