-1

Let us consider that I need to develop a program that reads 3 values and that prints these values in ascending order, using only if-else structures.

Notice that I know the classical sorting algorithms. But the point here is how to develop a sorting algorithm for 3 values using simple conditional structures.

I have implemented 2 versions. I need to identify which one is the most officient and why. Let us consider efficiency inversely proportional to the amount of time taken by the program.

I think that one way to measure this would be to count the minimum and the maximum amount of comparisons that are necessary. That is, to evaluate the best and the worst cases. But the number of conditions in the ifs are different in the two algorithms.

Let us ignore the time taken by printf.

Version 1:

#include <stdio.h>

int main()
{
    int v1,v2,v3;

    printf("Provide 3 values:\n");
    scanf("%d%d%d",&v1,&v2,&v3);

    if ( v1 <= v2 && v1 <= v3){
        if( v2 <= v3 ){
            printf("%d, %d, %d\n", v1, v2, v3);
        }
        else{
            printf("%d, %d, %d\n", v1, v3, v2);
        }
    }
    else{
        if(v2 <= v1 && v2 <= v3){
            if(v1 <= v3){
                printf("%d, %d, %d\n", v2, v1, v3);
            }
            else{
                printf("%d, %d, %d\n", v2, v3, v1);
            }
        }
        else{
            if(v2 <= v1){
                printf("%d, %d, %d\n", v3, v2, v1);
            }
            else{
                printf("%d, %d, %d\n", v3, v1, v2);
            }
        }
    }

    return 0;
}

Version 2

#include <stdio.h>

int main()
{
    int v1,v2,v3;

    printf("Provide 3 values:\n");
    scanf("%d%d%d",&v1,&v2,&v3);

    if ( v1 <= v2){
        if( v1 <= v3 ){
            if(v2 <= v3){
                printf("%d, %d, %d\n", v1, v2, v3);
            }
            else{
                printf("%d, %d, %d\n", v1, v3, v2);
            }
        }
        else{
            printf("%d, %d, %d\n", v3, v1, v2);
        }
    }
    else{
        if(v2 <= v3){
            if(v1 <= v3){
                printf("%d, %d, %d\n", v2, v1, v3);
            }
            else{
                printf("%d, %d, %d\n", v2, v3, v1);
            }
        }
        else{
            printf("%d, %d, %d\n", v3, v2, v1);
        }
    }

    return 0;
}

Is there some other program (that uses only if-else) that is more efficient than these two?

@rcgldr Can you show the code that implement your idea?

Version 3

int main()
{
    int v1,v2,v3;

    printf("Provide 3 values:\n");
    scanf("%d%d%d",&v1,&v2,&v3);

    if(v1 <= v2){
        if(v2 <= v3){
            printf("%d, %d, %d\n", v1, v2, v3);
        }else if(v1 <= v3 ){
            printf("%d, %d, %d\n", v1, v3, v2);
        }else{
            printf("%d, %d, %d\n", v3, v1, v2);
        }
    }
    else{
        if(v1 <= v3){
            printf("%d, %d, %d\n", v2, v1, v3);
        }else if(v2 <= v3){
            printf("%d, %d, %d\n", v2, v3, v1);
        }else{
            printf("%d, %d, %d\n", v3, v2, v1);
        }
    }
    return 0;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61
Zaratruta
  • 2,097
  • 2
  • 20
  • 26
  • have you tried looking at sorting algorithms? LIke merge-sort or anything like it? – murksiuke Mar 26 '19 at 18:45
  • 1
    How do you measure "efficiency"? – Eugene Sh. Mar 26 '19 at 18:48
  • Yes...I know the classical sorting algorithms. But the point is to develop a simple sorting algorithm for 3 numbers using only if-else structures. – Zaratruta Mar 26 '19 at 18:50
  • Efficiency here is related to the amount of time taken for running the program. – Zaratruta Mar 26 '19 at 18:50
  • The efficiency can either be the worst case efficiency, or the average case efficiency. Either way, you've got six possible orderings of the input variables, ending at six different print statements. So count the number of comparisons needed to reach the correct print statement, for each of the possible orderings. – user3386109 Mar 26 '19 at 18:51
  • Most time is bound to be spent trying to figure out what `Inform 3 values` is supposed to mean. – greybeard Mar 26 '19 at 18:52
  • Technically this is a very broad question without a simple answer, but if you're trying it for some kind of college assignment, probably the criteria is to achieve this going through the least number of steps possible. Even so there are two primary ways of interpreting the problem, you can minimize the number of steps by writing redundant code (like you are doing) or by minimizing the amount of code in general by making more intelligent routing of your algorithm. – Havenard Mar 26 '19 at 18:52
  • 2
    In *this* type of problems I would prefer the most *readable* code. – Eugene Sh. Mar 26 '19 at 18:54
  • 1
    For the 2 examples given; I'd expect CPU time consumed will be dominated by `printf()` (e.g. how many branches do you think there are converting an integer into "decimal ASCII"?); and (assuming the compiler's optimizer is enabled) I wouldn't be surprised if the output code is identical for both versions. – Brendan Mar 26 '19 at 18:54
  • 1
    I think a hand written bubble sort with three ifs and potentially three swaps is the fastest way. – Bathsheba Mar 26 '19 at 18:56
  • @user3386109...It is just a matter of curiosity. The assingment was to develop the programa. But I would like to develop the most efficient one. – Zaratruta Mar 26 '19 at 18:59
  • Must you use three separately named variables, or can you use an array? Your code just prints the values in the correct sequence without changing any data in memory — is that what's required? Could you copy the three variables into an array, sort the array, print the array? – Jonathan Leffler Mar 26 '19 at 19:00
  • @Zaratruta In that case, Bathsheba's comment is the answer. – user3386109 Mar 26 '19 at 19:01
  • 1
    @Zaratruta - assuming swaps are not allowed, then for the 6 possible permutations, it will take 5 if's and 5 else's as in version 2. If swaps are allowed, then 3 if / swap statements will work. – rcgldr Mar 26 '19 at 19:01
  • Your second piece of code cannot be improved from a performance perspective. I challenge anyone who disagrees to provide code. If you get lucky, you can tell in just two comparisons what the correct order is. However, in the worst case, you must do three comparisons. Your second program does all and only the required checks and is fully optimal for a correct solution. (this measures efficiency from a runtime perspective, not from a code length perspective; certainly code length could be shortened by swapping and whatnot). – Patrick87 Mar 26 '19 at 20:18
  • 1
    @Zaratruta - I forgot to mention, that although version 2 has 5 if, 5 else, all possible paths in that code use 3 compares. Changing the order of the 2nd level and 3rd level if statements uses 2 compares to 2 for 2 of 6 possible permutations, 3 compares for 4 of 6 possible permutations, for an average of 2 + 2/3 compares. – rcgldr Mar 26 '19 at 20:27
  • 1
    @rcgldr right and since execution efficiency is the metric, I contend code snippet 2 cannot be beaten. I'd love to (but won't) see code that can do bettern than 2 comparisons in the best case, 3 in the worst case, and 2+2/3 in the average case (assuming uniform distribution over the space of permutations). – Patrick87 Mar 26 '19 at 20:47
  • [O(1) solution](http://wiki.c2.com/?QuantumBogoSort) ;-) – chux - Reinstate Monica Mar 27 '19 at 01:22
  • @user3386109...I mean...The most efficient that satisfies the requirements...That is, the most efficient that uses only if-else structures – Zaratruta Mar 27 '19 at 12:25
  • @JonathanLeffler It is necessary to use 3 independent variables... – Zaratruta Mar 27 '19 at 12:26
  • @rcgldr Can you show the code that implement your idea? – Zaratruta Mar 27 '19 at 12:27
  • @Patrick87 Thank you! – Zaratruta Mar 27 '19 at 12:28
  • @Zaratruta - your question has been updated. – rcgldr Mar 27 '19 at 14:54

3 Answers3

1

Judging efficiency is difficult because it relies deeply on your CPU and your compiler's optimizer.

However, from a theoretic perspective, sorting 3 elements requires at least 3 comparisons. Sequence A036604 has values for larger numbers of elements.

Code for sorting 5 elements is shown here - you'll probably see why this kind of sorting isn't used often.

Richard
  • 56,349
  • 34
  • 180
  • 251
0

This is some code I created in association with a question SO 4203-5818 (that actually has little to do with sorting). It is for sorting arrays of 3 elements (sides of triangles in the other question), but isn't an answer to that question.

Assuming that you can/want to sort the data rather than just list it in sorted order, you could use one of the sort_3() variants shown in the code below, suitably adapted to your circumstances. It includes test code which tests every combination of 3 values selected from { 0, 1, 2 }. It uses 3 comparisons and up to 3 swaps to sort the data.

/* Sort 3 items - fixed comparisons */
/* Based on code for SO 4203-5818 */
#include <assert.h>
#include <stdio.h>

static inline void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Interesting: 4 of 6 permutations work, 2 fail */
#if P_01_02_12 + P_01_12_02 + \
    P_02_01_12 + P_02_12_01 + \
    P_12_01_02 + P_12_02_01 > 1
#error Too many of the control macros (P_[01][12]_[01][12]_[01][12]) are set
#endif
#if P_01_02_12 + P_01_12_02 + \
    P_02_01_12 + P_02_12_01 + \
    P_12_01_02 + P_12_02_01 == 0
#define P_02_01_12 1
#endif

#define P_STRING(x) static char const variant[] = #x

#ifdef P_01_02_12
P_STRING(P_01_02_12);
#endif
#ifdef P_01_12_02
P_STRING(P_01_12_02);
#endif
#ifdef P_02_01_12
P_STRING(P_02_01_12);
#endif
#ifdef P_02_12_01
P_STRING(P_02_12_01);
#endif
#ifdef P_12_01_02
P_STRING(P_12_01_02);
#endif
#ifdef P_12_02_01
P_STRING(P_12_02_01);
#endif

#if P_02_01_12
/* Working */
static void sort_3(int *a)
{
    if (a[0] > a[2]) swap(&a[0], &a[2]);
    if (a[0] > a[1]) swap(&a[0], &a[1]);
    if (a[1] > a[2]) swap(&a[1], &a[2]);
}
#endif /* 0 */

#if P_12_01_02
/* Triggers assertion */
static void sort_3(int *a)
{
    if (a[1] > a[2]) swap(&a[1], &a[2]);
    if (a[0] > a[1]) swap(&a[0], &a[1]);
    if (a[0] > a[2]) swap(&a[0], &a[2]);
}
#endif /* 0 */

#if P_01_12_02
/* Triggers assertion */
static void sort_3(int *a)
{
    if (a[0] > a[1]) swap(&a[0], &a[1]);
    if (a[1] > a[2]) swap(&a[1], &a[2]);
    if (a[0] > a[2]) swap(&a[0], &a[2]);
}
#endif /* 0 */

#if P_12_02_01
/* Working */
static void sort_3(int *a)
{
    if (a[1] > a[2]) swap(&a[1], &a[2]);
    if (a[0] > a[2]) swap(&a[0], &a[2]);
    if (a[0] > a[1]) swap(&a[0], &a[1]);
}
#endif /* 0 */

#if P_02_12_01
/* Working */
static void sort_3(int *a)
{
    if (a[0] > a[2]) swap(&a[0], &a[2]);
    if (a[1] > a[2]) swap(&a[1], &a[2]);
    if (a[0] > a[1]) swap(&a[0], &a[1]);
}
#endif /* 0 */

#if P_01_02_12
/* Working */
static void sort_3(int *a)
{
    if (a[0] > a[1]) swap(&a[0], &a[1]);
    if (a[0] > a[2]) swap(&a[0], &a[2]);
    if (a[1] > a[2]) swap(&a[1], &a[2]);
}
#endif /* 0 */

static void print_3(int *a)
{
    const char *pad = "";
    for (int i = 0; i < 3; i++)
    {
        printf("%s%d", pad, a[i]);
        pad = " ";
    }
}

static void check_3(int *a)
{
    assert(a[0] <= a[1]);
    assert(a[1] <= a[2]);
}

int main(void)
{
    printf("Variant: %s\n", variant);
    fflush(stdout);
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                int a[3] = { i, j, k };
                print_3(a);
                fputs(" : ", stdout);
                sort_3(a);
                print_3(a);
                putchar('\n');
                check_3(a);
            }
        }
    }
    return 0;
}

You can find this code in my SOQ (Stack Overflow Questions) repository on GitHub as files st13.c (and st17.c and st19.c for variants on the idea) in the src/so-4203-5818 sub-directory. Note that st19 (and the test script test.st19.sh) show that there are 6 possible working sorts — 01:02:12, 01:12:01, 02:01:12, 02:12:01, 12:01:12, 12:02:01 — out of a 27 (33) possible combinations. (The 01:12:01 and 12:01:12 working variants are not demonstrated in st13 but can be demonstrated by st19.)

If you must sort 3 variables with disjoint names, then you can adapt any of the working array-sorting functions to work inline. For example, using the P_01_02_12 variant to sort v0, v1, v2, you'd end up with:

if (v0 > v1) swap(&v0, &v1);
if (v0 > v2) swap(&v0, &v2);
if (v1 > v2) swap(&v1, &v2);
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • This cannot be more efficient from a number-of-comparisons perspective than the second code sample. If I'm wrong, I'd love to see the actual generated code (either the intermediate with everything inlined or the reconstituted assembly code). I am reasonably certain that 2 comparisons on 2 cases and 3 comparisons on 4 cases is theoretically optimal. – Patrick87 Mar 26 '19 at 20:25
  • I'm unsure what you mean by "2 comparisons on 2 cases". In my terminology, if there are 2 values to be sorted, 1 comparison is sufficient to determine whether they're in order or not. I'm also unsure about "3 comparisons on 4 cases". This skips the "3 cases" or "3 values to be sorted" scenario, which is the one the code addresses — and for that, in the general case, 3 comparisons are necessary and sufficient. I've not scrutinized the "4 values to be sorted" scenario myself, but I am lead to believe (from [Sequence A036604](https://oeis.org/A036604) that 5 comparisons are necessary for that. – Jonathan Leffler Mar 26 '19 at 20:35
  • 1
    Sorry, what I meant is that there are 6 permutations and potentially only one of those 6 permutations corresponds to an ordered sequence of the 3 elements. I contend that no method for determining the correct order will use fewer than 3 comparisons in the worst case, nor can any use fewer than two comparisons in the best case. Furthermore, I contend that no method for determining the correct order can have more than two cases that require just 2 comparisons. – Patrick87 Mar 26 '19 at 20:44
  • I agree that "no method … will use fewer than 3 comparisons in the worst case". Thinking about it, AFAICS, the only time that 2 comparisons are sufficient is when the data is already sorted. If the data is not in sorted order, the third comparison will be needed. – Jonathan Leffler Mar 26 '19 at 20:54
  • @JonathanLeffler - swapping the inner two levels of if's in the question's version 2, uses 2 compares for v1 <= v2 <= v3 or v2 < v1 <= v3, so 2 of the 6 possible permutations, for average number of 2 2/3 compares. The sequence is basically compare any two values, then compare the larger of those two values with the third remaining value, and if that larger value is <= third remaining value, the sort is done after just 2 compares. – rcgldr Mar 26 '19 at 23:24
  • If (v1 <= v2) { if (v2 <= v3) { // v1 <= v2 <= v3 // } else { ... }} else { if (v2 <= v3) ( ... } else { // v3 < v2 < v1 // }}. I think you get by with 2 comparisons if you structure them right for both the sorted AND reverse-sorted cases. – Patrick87 Mar 27 '19 at 01:21
-1

Forgive that this is not if-then-else, but here is three tests, and six assignments (three in the pass by copy, three in the compound literal construction.

#include <assert.h>
struct triplet
{
    int i1, i2, i3;  //  least, middle, greatest
};

// convert triplet order to lowest to highest
struct triplet order3(struct triplet in)
{
    return 
    ( in.i1 > in.i2 ?
      (in.i3 > in.i1 ? 
          (struct triplet){.i3=in.i3, .i2=in.i1, .i1=in.i2}  
         :(in.i3 > in.i2 ?
             (struct triplet){.i3=in.i1, .i2=in.i3, .i1=in.i2} 
           : (struct triplet){.i3=in.i1, .i2=in.i2, .i1=in.i3}))
    : (in.i3 > in.i2 ? 
          (struct triplet){.i3=in.i3, .i2=in.i2, .i1=in.i1}  
        : (in.i3 > in.i1 ? 
             (struct triplet){.i3=in.i2, .i2=in.i3, .i1=in.i1} 
           : (struct triplet){.i3=in.i2, .i2=in.i1, .i1=in.i3}))
    );
}

void testIt(struct triplet in)
{
    assert(in.i3 > in.i2);
    assert(in.i2 > in.i1);
}

void main(void)
{

    testIt(order3((struct triplet){10,20,30}));
    testIt(order3((struct triplet){20,10,30}));    
    testIt(order3((struct triplet){30,10,20}));
    testIt(order3((struct triplet){10,30,20}));
    testIt(order3((struct triplet){20,30,10}));
    testIt(order3((struct triplet){30,20,10}));    

}
bd2357
  • 704
  • 9
  • 17