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

Groups > comp.lang.c > #75165

Re: Program to sort three integers

Show all headers | View raw

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

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

In a swap routine, it's traditional to call the temporary variable
something like "temp".  I like to call it something like "old_x"
because it makes it very clear what value it holds, and I don't have
to stop and think *quite* as hard to avoid doing the assignments
in the wrong order (yes, I've made that mistake).  Also, defining
it as "const" guarantees that I won't incorrectly re-assign to it.
(It's not really "old_x", it's really "old_star_x" -- but in this
case terseness and clarity win out over pedantic correctness.)

Since I wasn't quite 100% confident that my algorithm would cover all
cases, I wrote code to test it for all cases.  A more thorough test
framework would verify that the result is actually sorted and that
the output contains the same numbers as the input, but for something
this small visual examination of the output is good enough.  I test
all 6 permutations of 3 distinct values.  If I wanted to be truly
exhaustive, I'd test all the cases where two or more of the values
are equal, but I only bothered doing a couple (3,1,1 and 3,3,1).
I also assume that if sorting 2,1,3 works correctly, sorting 20,10,30
will also work correctly; I can justify that assumption because I
know that the function depends only on "<" comparisons.

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.

-- 
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"

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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