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 3 of 3 — ← Prev page 1 2 [3]

#75205

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
<snip>
> 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.

That last line should be "sort5 uses 27..." of course.

-- 
Ben.

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

#75236

<snip>
> You'll note that there are no comments.  I'd like to think that
> my code is clear enough, including the choice of names, that it
> doesn't need them.
> 
Thank you very much for this code; yes, it is clear. I am glad to 
see the 'try' function that allows to test permutations. 

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

#75241

The original code seems way too complex for doing such a simple task.

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

#75232

> 
> Okay, let's start off by implementing it correctly, so that we have 
> something to compare against:
> 
> #include <stdio.h>
> 
> void swap(int *left, int *right)
> {
>    int tmp = *left;
>    *left = *right;
>    *right = tmp;
> }
> 
> void sort(int *a, int *b, int *c)
> {
>    if(*a > *b)
>    {
>      swap(a, b);
>    }
>    /* The value at *a is now smaller than that at *b */
>    if(*b > *c)
>    {
>      swap(b, c);
>    }
>    /* The value at *c is now definitely the biggest, but *b
>       could now hold a value smaller than *a, so check again. */
>    if(*a > *b)
>    {
>      swap(a, b);
>    }
> }
> 
> int main(void)
> {
>    int i = 3;
>    int j = 1;
>    int k = 9; /* your own data */
> 
>    printf("Before: %d %d %d\n", i, j, k);
> 
>    sort(&i, &j, &k);
> 
>    printf(" After: %d %d %d\n", i, j, k);
> 
>    return 0;
> }
> 
> Result:
> 
> Before: 3 1 9
>   After: 1 3 9
> 

This is so elegant. I wish I had come up with the same version. 
My one looks cumbersome.

Thank you :)

> These are pointers-to-int. You can use them for pointing to ints, but at 
> present you haven't pointed them anywhere. Their values are 
> "indeterminate", which means we don't know what those values are. That 
> is, we have no guarantee that they are pointing anywhere useful or safe.
> 
Yes, I have finally understood this issue.

> > Another important issue which both versions have revealed again:
> > I do not understand how to make a function return several values;
> 
> Neither do I. If you find out, let me know.
:)

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

#75144

On Fri, 6 Nov 2015 08:20:08 -0800 (PST), Alla _
<modelling.data@gmail.com> wrote:

>Hello!
>
>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.)
>
>I have written two options, none compile because of my fundamental
>misunderstandings of the way pointers work, and also return values
>of functions.

There is more to programming than just coding.  One aspect is
understanding how skills you already have can be used to solve a new
problem.

In a previous discussion, you created a function that will sort an
array N of integers.  What would happen if your new program assigned
the three integers to elements of an array of three int and then
called the function you already have?

-- 
Remove del for email

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

#75146

On 06/11/15 18:14, Barry Schwarz wrote:
> On Fri, 6 Nov 2015 08:20:08 -0800 (PST), Alla _
> <modelling.data@gmail.com> wrote:
>
>> Hello!
>>
>> 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.)
>>
>> I have written two options, none compile because of my fundamental
>> misunderstandings of the way pointers work, and also return values
>> of functions.
>
> There is more to programming than just coding.  One aspect is
> understanding how skills you already have can be used to solve a new
> problem.
>
> In a previous discussion, you created a function that will sort an
> array N of integers.  What would happen if your new program assigned
> the three integers to elements of an array of three int and then
> called the function you already have?

What would happen is that the program would not meet the specification, 
which forbids the usage of an array within the sort() function, and you 
would need an array, even though you are only using it for setting up 
the my_previous_function_for_sorting_an_array() function call.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#75162

Alla _ <modelling.data@gmail.com> writes:

> 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.)
>
> I have written two options, none compile because of my fundamental
> misunderstandings of the way pointers work, and also return values
> of functions.  [snip sample programs]

I am somewhat relucant to reply because I'm not really responding
to the questions you ask.  However there are some lessons to
learn that I think should take precedence over the issues you
are currently asking about.

The basic principle is this:  rather than thinking about what's
going on at the bottom of what the program will do, think first
about what needs to go on at a higher level;  look at the bigger
picture first, and only after that is more or less worked out
should you concern yourself with lower level details.

So first, let's simplify part of the task.  Rather than looking
at three values, let's take the case of just two.  We have two
variables 'a' and 'b' - if they are in the right order already
then everything is okay, and if they aren't then we would like to
exchange the values.  We don't (yet) write code to do that, but
just propose a function that will do it for us.  Here is a
possible declaration for such a function:

    void swap_if_out_of_order( int *pa, int *pb );

If we presume this function exists, and does what the name
implies -- namely, if the item pointed to by 'pa' is out of order
with respect to the item pointed to by 'pb', then those two
pointed-to items are exchanged -- then it is easy to write a
function to sort three int values:

    void
    sort( int *pa, int *pb, int *pc ){
        swap_if_out_of_order( pa, pb );
        swap_if_out_of_order( pb, pc );
        swap_if_out_of_order( pa, pb );
    }

Can you see how this function works and why?  If not please ask.
Briefly, the first two function calls ensure the last pointed-to
item has the right value, but the first two pointed-to items may
be out of order;  then the third (ie, last) function call takes
care of the first two items (if that is needed).

Now we return to the matter of swap_if_out_of_order().  Because
it considers only two values, it can be written very succinctly:

    void
    swap_if_out_of_order( int *pa, int *pb ){
        int a = *pa, b = *pb;
        if(  a > b  )  *pa = b,  *pb = a;
    }

With this function written, our sort() routine is complete.

Incidentally, note that writing the code this way should make it
easier to see what is going on with the pointers, because the
part of the code that deals with pointer indirection has gotten
a lot smaller.  If you can understand just these two lines, then
what is going on with pointers and "returning" several values
should also be understandable.

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

#75235

> The basic principle is this:  rather than thinking about what's
> going on at the bottom of what the program will do, think first
> about what needs to go on at a higher level;  look at the bigger
> picture first, and only after that is more or less worked out
> should you concern yourself with lower level details.
> 
> So first, let's simplify part of the task.  Rather than looking
> at three values, let's take the case of just two.  We have two
> variables 'a' and 'b' - if they are in the right order already
> then everything is okay, and if they aren't then we would like to
> exchange the values.  We don't (yet) write code to do that, but
> just propose a function that will do it for us.  Here is a
> possible declaration for such a function:
> 
>     void swap_if_out_of_order( int *pa, int *pb );
> 
> If we presume this function exists, and does what the name
> implies -- namely, if the item pointed to by 'pa' is out of order
> with respect to the item pointed to by 'pb', then those two
> pointed-to items are exchanged -- then it is easy to write a
> function to sort three int values:
> 
>     void
>     sort( int *pa, int *pb, int *pc ){
>         swap_if_out_of_order( pa, pb );
>         swap_if_out_of_order( pb, pc );
>         swap_if_out_of_order( pa, pb );
>     }
> 
> Can you see how this function works and why?  If not please ask.
> Briefly, the first two function calls ensure the last pointed-to
> item has the right value, but the first two pointed-to items may
> be out of order;  then the third (ie, last) function call takes
> care of the first two items (if that is needed).
> 
> Now we return to the matter of swap_if_out_of_order().  Because
> it considers only two values, it can be written very succinctly:
> 
>     void
>     swap_if_out_of_order( int *pa, int *pb ){
>         int a = *pa, b = *pb;
>         if(  a > b  )  *pa = b,  *pb = a;
>     }
> 
> With this function written, our sort() routine is complete.
> 
> Incidentally, note that writing the code this way should make it
> easier to see what is going on with the pointers, because the
> part of the code that deals with pointer indirection has gotten
> a lot smaller.  If you can understand just these two lines, then
> what is going on with pointers and "returning" several values
> should also be understandable.

Thank you very much. Yes, I see how it works. 

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

#75231

On Friday, November 6, 2015 at 4:20:25 PM UTC, Alla _ wrote:
> Hello!
> 
> 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.)
> 
You need to separate in your mind the sort algorithm from the messing
about with pointers.
Let's start with the simplest sort algorithm, exhaustive enumeration.
its 3!, which since we have three integers, is six cases. A bit too
many for comfort. But OK.

So start with a skeleton fucntion

void sort(int *a, int *b, int *c)
{
  if(*a < *b && *a < *c & *b < *c)
  {
     printf("abc\n");
  }
  else if( /* you write this */)
  {
     printf("acb\n");
  }
} 

fill out that function, then write  a test loop to generate a hundred sets of random integers with small values (say 0, 1 or 2) and see if it always
gets the right answer.

That's the sort algorithm sorted.

Now for filling in. That's easy to do inefficiently. Just take three
integers, first, second, and third, assign them, then write out to
*a, *b, *c.
So do that. Now you've achieved a working function. Often we just
leave it at that.

But we can then start thinking about how to make the function more
efficient. 

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

#75542

On 06.11.2015 17:20, Alla _ wrote:
>
> Another important issue which both versions have revealed again:
> I do not understand how to make a function return several values;
> for example, if the function computes 3 values, how can I make it
> return all three of them to use in the main function?

Use array, for values of the same type...

 >(This function is not to be implemented with arrays.)

Ops;)

Use structs.

typedef struct {
     int a,b,c;
} ans ;

ans sort_3 (int a, int b, int c)
{
     if (b<a) { /*swap*/  int tmp = a; a=b; b=tmp; }
     if (b<c) return (ans){a,b,c};
     else // a<b c<b
         if (a<c) return (ans){a,c,b};
         else return (ans){c,a,b};
}
ans sort_3_without_swap (int a, int b, int c)
{
     if (a<b) {
         if (b<c) return (ans){a,b,c};
         else // a<b c<b
             if (a<c) return (ans){a,c,b};
             else return (ans){c,a,b};
     }else{
         if (a<c) return (ans){b,a,c};
         else // b<a c<a
             if (b<c) return (ans){b,c,a};
             else return (ans){c,b,a};
     }
}

Testing:
int main(void)
{

     int a,b,c;
     for (a=0;a<3;a++)
         for (b=0;b<3;b++)
             for (c=0;c<3;c++){
                 ans w = sort_3(a,b,c);
                 printf("sw %d %d %d (%d)\n",w.a,w.b,w.c, w.a<=w.b&& 
w.b<=w.c);
                 w=sort_3_without_swap(a,b,c);
                 printf("ws %d %d %d (%d)\n",w.a,w.b,w.c, w.a<=w.b&& 
w.b<=w.c);
             }
      return 0;
}


Now do it for five elements! :->
As you saw, swapping two elements let us avoid some branches in the code.

I don't know if C use (N)RVO, it can be slightly slower
than pointer version.

You can also join the Dark Side, install c++, and use tuples ;-)

bartekltg

[toc] | [prev] | [standalone]

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

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

csiph-web