Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #75113 > unrolled thread

Program to sort three integers

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#75170

On 06/11/2015 19:36, Keith Thompson wrote:


> void sort2(int *x, int *y) {
>      if (*x > *y) {
>          const int old_x = *x;
>          *x = *y;
>          *y = old_x;
>      }
> }

I'd question the benefit of using 'const' here. Actually I found it 
distracted from the code (the out-of-sequence declaration, which also 
renders the first assignment out of alignment, doesn't help).

A variable has value stored it it, then that value is used just once, 
two lines later, and the function returns. What would happen without the 
const?

And why not also write:

  void sort2(int * const x, int * const y) ?

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#75182

Bartc <bc@freeuk.com> writes:
> On 06/11/2015 19:36, Keith Thompson wrote:
>> void sort2(int *x, int *y) {
>>      if (*x > *y) {
>>          const int old_x = *x;
>>          *x = *y;
>>          *y = old_x;
>>      }
>> }
>
> I'd question the benefit of using 'const' here. Actually I found it 
> distracted from the code (the out-of-sequence declaration, which also 
> renders the first assignment out of alignment, doesn't help).

Noted.

> A variable has value stored it it, then that value is used just once, 
> two lines later, and the function returns. What would happen without the 
> const?

One thing that *could* happen is that if I mixed up the assignments and
assigned a new value to old_x, the compiler would catch it for me.

I like to define things as const *unless* I'm going to be modifying
them.  If I follow that consistently, then an object defined without
const stands out and implies that I'm going to want to modify it.

I understand not everyone follows that convention.

> And why not also write:
>
>   void sort2(int * const x, int * const y) ?

Good question.  If I were to be 100% consistent then yes, I'd define
the parameters as const.  There are several reasons I don't bother,
none of them really good.  One is that I like to keep parameter
declarations in function declarations and definitions consistent,
and the const is meaningless in a declaration.  Another is that I
stumble briefly over the ordering of "*" and "const", so omitting
"const" makes it a little easier to read.

(As I've probably mentioned too many times, in my dream language objects
would be read-only by default, and you'd have to add a keyword if you
want to be able to change them after initialization.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#75449

On Fri, 2015-11-06, Keith Thompson wrote:
> Bartc <bc@freeuk.com> writes:
>> On 06/11/2015 19:36, Keith Thompson wrote:
>>> void sort2(int *x, int *y) {
>>>      if (*x > *y) {
>>>          const int old_x = *x;
>>>          *x = *y;
>>>          *y = old_x;
>>>      }
>>> }
>>
>> I'd question the benefit of using 'const' here. Actually I found it 
>> distracted from the code (the out-of-sequence declaration, which also 
>> renders the first assignment out of alignment, doesn't help).
>
> Noted.
>
>> A variable has value stored it it, then that value is used just once, 
>> two lines later, and the function returns. What would happen without the 
>> const?
>
> One thing that *could* happen is that if I mixed up the assignments and
> assigned a new value to old_x, the compiler would catch it for me.
>
> I like to define things as const *unless* I'm going to be modifying
> them.  If I follow that consistently, then an object defined without
> const stands out and implies that I'm going to want to modify it.
>
> I understand not everyone follows that convention.

Here's another one who does (except maybe in super-small scopes like
this one).

>> And why not also write:
>>
>>   void sort2(int * const x, int * const y) ?
>
> Good question.  If I were to be 100% consistent then yes, I'd define
> the parameters as const.  There are several reasons I don't bother,
> none of them really good.  One is that I like to keep parameter
> declarations in function declarations and definitions consistent,
> and the const is meaningless in a declaration.  Another is that I
> stumble briefly over the ordering of "*" and "const", so omitting
> "const" makes it a little easier to read.

If you're open to changing your mind about this, I can warmly
recommend doing it.  Parameters have large scopes and are probably
used a lot, so the benefit of reading "oh, it's const; I don't have to
worry about accidental modifications further down" is fairly big.

It doesn't bother me at all that the declaration and definition don't
match.  I think of it as the definition having more responsibilities
(which happen to concern only itself).

> (As I've probably mentioned too many times, in my dream language objects
> would be read-only by default, and you'd have to add a keyword if you
> want to be able to change them after initialization.)

There are always the functional languages ...

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#75452

On 09/11/15 14:36, Jorgen Grahn wrote:
> On Fri, 2015-11-06, Keith Thompson wrote:
>> Bartc <bc@freeuk.com> writes:

>>> And why not also write:
>>>
>>>   void sort2(int * const x, int * const y) ?
>>
>> Good question.  If I were to be 100% consistent then yes, I'd define
>> the parameters as const.  There are several reasons I don't bother,
>> none of them really good.  One is that I like to keep parameter
>> declarations in function declarations and definitions consistent,
>> and the const is meaningless in a declaration.  

Why not put the "const" in the declaration as well as the definition,
and then be both const and consistent?

>> Another is that I
>> stumble briefly over the ordering of "*" and "const", so omitting
>> "const" makes it a little easier to read.

In cases like this one, I agree - it is too easy to misread it as

	void sort2(int const * x, int const * y)

> 
> If you're open to changing your mind about this, I can warmly
> recommend doing it.  Parameters have large scopes and are probably
> used a lot, so the benefit of reading "oh, it's const; I don't have to
> worry about accidental modifications further down" is fairly big.
> 
> It doesn't bother me at all that the declaration and definition don't
> match.  I think of it as the definition having more responsibilities
> (which happen to concern only itself).
> 

[toc] | [prev] | [next] | [standalone]

#75614

Keith Thompson <kst-u@mib.org> wrote:

> (As I've probably mentioned too many times, in my dream language objects
> would be read-only by default, and you'd have to add a keyword if you
> want to be able to change them after initialization.)

That's academically desirable, but I'm afraid that in the real world
that would apply to most objects you use, and therefore, be a pain in
the fundament (and therefore, your language would go unused).

Richard

[toc] | [prev] | [next] | [standalone]

#75625

raltbos@xs4all.nl (Richard Bos) writes:
> Keith Thompson <kst-u@mib.org> wrote:
>> (As I've probably mentioned too many times, in my dream language objects
>> would be read-only by default, and you'd have to add a keyword if you
>> want to be able to change them after initialization.)
>
> That's academically desirable, but I'm afraid that in the real world
> that would apply to most objects you use, and therefore, be a pain in
> the fundament (and therefore, your language would go unused).

You may be right -- but I've often found that most of the objects
I define don't change their values after they're initialized.
This assumes that you can define them only after you have enough
information to compute their initial values; the ability to mix
declarations and statements makes this much easier.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#75627

On Tuesday, November 10, 2015 at 10:56:31 AM UTC-6, Richard Bos wrote:
> Keith Thompson wrote:
> > (As I've probably mentioned too many times, in my dream language objects
> > would be read-only by default, and you'd have to add a keyword if you
> > want to be able to change them after initialization.)
> 
> That's academically desirable, but I'm afraid that in the real world
> that would apply to most objects you use, and therefore, be a pain in
> the fundament (and therefore, your language would go unused).

Many languages could benefit from better recognition of different kinds of
immutability.  For example, there are two semantically-useful kinds of
"pointer to const object":

    1. The passed-in pointer will never be used to modify the object outside
       the control of the code that passes it in.

    2. The passed-in pointer will never be used to modify the object.

There are many situations where it may be necessary for a routine to have a
pointer "pass through" it to a caller-designated recipient (either returning
it to the caller or passing it to a caller-specified function) without using
the pointer itself.  The routine knows that it will never modify the pointer,
but can make no such assertion on behalf of the recipient.

The second kind of pointer would allow many optimization opportunities not
available with the first, but there are many situations where the first is
semantically required.

Also, a concept I'd like to see in a language would be a form of identifier
which would work something like a variable except that repeated declarations
would be allowed within a scope *but* re-assignments without re-declaration
would not, and such identifiers may only be read in places where no path
from the last declaration to the usage would contain any other declaration.
Under such semantics, reading backward through the code from any reference
to such an identifier would make it possible to identify where it was
written [the only time there would be multiple possibilities would be:

    if (condition)
    {
      define int foo = expr1; // whatever syntax
    }
    else
    {
      define int foo = expr2;
    }

and in that situation "foo" would only be usable after the "if" if both
branches of the "if" contained declarations of the same type.  There are
cases where code needs a more "free-usage" style of variable, but I would
suggest that there are a lot of situations where there would be great
value in being able to very easily pair up places an identifier is used
with places where it is set.

[toc] | [prev] | [next] | [standalone]

#75711

Richard Bos wrote:
> Keith Thompson <kst-u@mib.org> wrote:
>
>> (As I've probably mentioned too many times, in my dream language objects
>> would be read-only by default, and you'd have to add a keyword if you
>> want to be able to change them after initialization.)
>
> That's academically desirable, but I'm afraid that in the real world
> that would apply to most objects you use, and therefore, be a pain in
> the fundament (and therefore, your language would go unused).
>
> Richard
>


I have to agree with Keith on this - for some reason, having
to remove "const" from all declarations turns out to be
an excellent review technique.

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#75172

Keith wrote:
void sort3(int *x, int *y, int *z) { 
    sort2(x, y); 
    sort2(y, z); 
    sort2(x, y); 
}
------
For me should be 
void sort3(int *x, int *y, int *z) { 
    sort2(x, y); 
    sort2(y, z); 
    sort2(x, z); 
}

[toc] | [prev] | [next] | [standalone]

#75173

On 06/11/2015 19:52, asetofsymbols@gmail.com wrote:
> Keith wrote:
> void sort3(int *x, int *y, int *z) {
>      sort2(x, y);
>      sort2(y, z);
>      sort2(x, y);
> }
> ------
> For me should be
> void sort3(int *x, int *y, int *z) {
>      sort2(x, y);
>      sort2(y, z);
>      sort2(x, z);
> }

This doesn't sort (30, 20, 10).

[toc] | [prev] | [next] | [standalone]

#75176

Bart wrote:

On 06/11/2015 19:52, asetof...@gmail.com wrote: 
> Keith wrote: 
> void sort3(int *x, int *y, int *z) { 
>      sort2(x, y); 
>      sort2(y, z); 
>      sort2(x, y); 
> } 
> ------ 
> For me should be 
> void sort3(int *x, int *y, int *z) { 
>      sort2(x, y); 
>      sort2(y, z); 
>      sort2(x, z); 
> } 


This doesn't sort (30, 20, 10).
------
 if > swap
[x y z] = [30, 20, 10]
sort2(x, y); 
[x y z] = [20, 30, 10]
sort2(y, z); 
[x y z] = [20, 10, 30]
sort2(x, z); 
[x y z] = [20, 10, 30]

Yes my error seems not right
the last: sort2(x, z); 

Should be right 
sort2(x, y); as in Keith post
Thanks 

[toc] | [prev] | [next] | [standalone]

#75177

"Bartc" write:

> On 06/11/2015 19:52, asetofsymbols@gmail.com wrote:
>> Keith wrote:
>> void sort3(int *x, int *y, int *z) {
>>      sort2(x, y);
>>      sort2(y, z);
>>      sort2(x, y);
>> }
>> ------
>> For me should be
>> void sort3(int *x, int *y, int *z) {
>>      sort2(x, y);
>>      sort2(y, z);
>>      sort2(x, z);
>> }
> 
> This doesn't sort (30, 20, 10).

Yes, it's a nice little problem. 

[toc] | [prev] | [next] | [standalone]

#75184

Keith Thompson <kst-u@mib.org> writes:

> Richard Heathfield <rjh@cpax.org.uk> writes:
>> On 06/11/15 16:20, Alla _ wrote:
>>> Here is the description of the task:
>>>
>>> Write a function called sort() to sort three integers into ascending
>>> order. (This function is not to be implemented with arrays.)

<snip>
> I found this to be an interesting problem, so I went ahead and
> threw together a solution.

I used to set it as an exercise but I asked that the students add

  assert(*a <= *b && *b <= *c);

just before returning.  The twist being the follow-up exercise: to call
sort so that the assert fails!

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#75190

In article <lnoaf63oo6.fsf@kst-u.example.com>,
 Keith Thompson <kst-u@mib.org> wrote:

> I found this to be an interesting problem, so I went ahead and
> threw together a solution.  I was hesitant to post a full solution,
> but since you've already done so here goes.
> 
> #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);
> }
> 
> void try(int a, int b, int c) {
>     printf("%d %d %d -> ", a, b, c);
>     sort3(&a, &b, &c);
>     printf("%d %d %d\n", a, b, c);
> }
> 
> int main(void) {
>     try(3, 1, 1);
>     try(3, 3, 1);
>     try(1, 2, 3);
>     try(1, 3, 2);
>     try(2, 1, 3);
>     try(2, 3, 1);
>     try(3, 1, 2);
>     try(3, 2, 1);
> }
> 
> For sorting N items, where you don't know N until run time, you have
> to write general code.  (There are more general-purpose sorting
> algorithms out there than you can shake a stick at.)  If you know
> that N==3, you can do something more specific by recognizing that
> sorting the first two items, then the last two items, then the
> first two items, solves the problem.  (If I needed to sort 4 items,
> I *might* try to come up with a custom solution, but it would
> probably be easier to call an existing general sorting routine.)

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.

Now could a macro be written to generate those functions? (I've never 
done much with the C preprocessor.)

[toc] | [prev] | [next] | [standalone]

#75191

In article <mstorkamp-6548C9.16045906112015@88-209-239-213.giganet.hu>,
 Mark Storkamp <mstorkamp@yahoo.com> wrote:

> In article <lnoaf63oo6.fsf@kst-u.example.com>,
>  Keith Thompson <kst-u@mib.org> wrote:
> 
> > I found this to be an interesting problem, so I went ahead and
> > threw together a solution.  I was hesitant to post a full solution,
> > but since you've already done so here goes.
> > 
> > #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);
> > }
> > 
> > void try(int a, int b, int c) {
> >     printf("%d %d %d -> ", a, b, c);
> >     sort3(&a, &b, &c);
> >     printf("%d %d %d\n", a, b, c);
> > }
> > 
> > int main(void) {
> >     try(3, 1, 1);
> >     try(3, 3, 1);
> >     try(1, 2, 3);
> >     try(1, 3, 2);
> >     try(2, 1, 3);
> >     try(2, 3, 1);
> >     try(3, 1, 2);
> >     try(3, 2, 1);
> > }
> > 
> > For sorting N items, where you don't know N until run time, you have
> > to write general code.  (There are more general-purpose sorting
> > algorithms out there than you can shake a stick at.)  If you know
> > that N==3, you can do something more specific by recognizing that
> > sorting the first two items, then the last two items, then the
> > first two items, solves the problem.  (If I needed to sort 4 items,
> > I *might* try to come up with a custom solution, but it would
> > probably be easier to call an existing general sorting routine.)
> 
> 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.
> 
> Now could a macro be written to generate those functions? (I've never 
> done much with the C preprocessor.)

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);

[toc] | [prev] | [next] | [standalone]

#75195

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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#75704

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?

[toc] | [prev] | [next] | [standalone]

#75793

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.

[toc] | [prev] | [next] | [standalone]

#75799

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

[toc] | [prev] | [next] | [standalone]

#75196

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.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web