Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Program to sort three integers |
| Date | 2015-11-11 23:50 +0100 |
| Organization | ATMAN - ATM S.A. |
| Message-ID | <n20go0$ph$1@node2.news.atman.pl> (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> <mstorkamp-B3F014.16085906112015@88-209-239-213.giganet.hu> |
On 06.11.2015 23:08, Mark Storkamp wrote:
> 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);
Cost:
T(n) = 2*T(n-1) +1
T(n) = 2^n-1
Meh. But still faster than slowsort.
https://en.wikipedia.org/wiki/Bogosort
:-)
But we are interested only in small arrays.
We can sort 3 elements using 3 comparations.
For 4 the best algorithm uses 5. Your algorithm
uses 7. Not bad. But for 5 it is 7+7+1=15,
the best results is 7.
Rick C. Hodgin have written a solution for 3 elements as a sequence
of operation 'swap if not in order'.
This method is very similar to the sorting networks.
https://en.wikipedia.org/wiki/Sorting_network
They are created to solve different problems (hardware can do swap_if
simultaneously, so the 'depth' is important, not number of operation),
but it still give us decent solutions. Perfecet for cases 3 and 4.
n 3 4 5 6 7 8
Optimal 3 5 7 10 13 16
Sorting net 3 5 9 12 16 19
Recursive 3 7 15 31 63 127
There methods to create sorting algorithm for arrays bigger than 16,
the are not optimal, but I cant find the paper.
bast
bartekltg
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