Finding the middle number of five integer numbers

Question

The code below shows the middle number out of three numbers. How can I do the same thing for five numbers?

By repeating the same logic for five numbers or is there a much better way of doing that?

#include <stdio.h>
#include <stdlib.h>

int main() {
    int num1, num2, num3;
    printf("Enter three numbers\n");
    scanf("%d %d %d", &num1, &num2, &num3); // takes input from user
    // checking num1 is a middle number or not
    if (num2 > num1 && num1 > num3 || num3 > num1 && num1 > num2) {
        printf("\n%d is a middle number", num1);
    }
    //checking num2 is a middle number or not
    if (num1 > num2 && num2 > num3 || num3 > num2 && num2 > num1) {
        printf("\n%d is a middle number", num2);
    }
    //checking num3 is a middle number or not
    if (num1 > num3 && num3 > num2 || num2 > num3 && num3 > num1) {
        printf("\n%d is a middle number", num3);
    }
    
    return 0;
}

How about reading the numbers into an array and sorting it then pointing to the 3rd element? — Nino, Jun 05 '22 at 14:54
Note that the 3-number code doesn't produce an answer if any two of the numbers are the same. — Jonathan Leffler, Jun 05 '22 at 14:57
Simply sorting and reading the middle element won't be "the same thing" because sorting will work with the case where all numbers are the same while the code posted here won't. — MikeCAT, Jun 05 '22 at 14:59
Finding the median among five elements is known to be doable in six comparisons in total. https://cstheory.stackexchange.com/questions/12257/exact-number-of-comparisons-to-compute-the-median — , Jun 05 '22 at 15:01
Generalizing this is basically what [`std::nth_element` is for in C++](https://en.cppreference.com/w/cpp/algorithm/nth_element), which gets an average case linear time solution. — ShadowRanger, Jun 05 '22 at 15:06
There's even a [qsort](https://en.cppreference.com/w/c/algorithm/qsort) function in stdlib.h that will help you solve this. — Chris, Jun 05 '22 at 15:07
@Chris: Yeah, that's why it's not an answer. :-) That said, the algorithm used by `nth_element` is what you'd want if you were generalizing this for any arbitrary `n`, since the larger `n` gets, the worse the `O(n log n)` cost of generalized sort is. — ShadowRanger, Jun 05 '22 at 21:59

score 1 · Accepted Answer · answered Jun 05 '22 at 17:22

By repeating the same logic for five numbers or is there a much better way of doing that?

It depends on exactly what you mean by "repeating the same logic" and on how you measure "better".

It is possible to determine the median of five items with use of just six comparisons (but no fewer). In principle, this could be coded as a pure decision tree (no swaps or use of temporary variables). That would be a pretty close five-element analog of the code presented in the question. It would be very efficient, and it would not modify the input, but it would be hard to read or understand (not to mention long).

It would also be possible to introduce some temporary variables to that decision-tree approach that would make it shorter somewhat easier to follow, at the cost of a small amount of overhead and probably a little less computational efficiency.

Or it would be possible to sort the input and choose the middle element from the result. That could be fairly easy to understand, depending on implementation details, but it would be much less efficient.

Or it would be possible to implement a partial sort to save a little time vs a full sort, yet still be pretty clear (at the point of use, but not necessarily overall). An early-terminating selection sort could do this, or a quickselect implementation. These are still comparatively less efficient than the decision-tree style approaches, and rather more code.

If efficiency were a key consideration then I would at least test this variation on the "decision tree with temporaries" approach:

int median_of_five(int a, int b, int c, int d, int e) {
    struct pair { int x, y; };
    struct pair temp1;
    struct pair temp2;
    struct pair pair1;
    struct pair pair2;

    // arrange a, b, c, and d into two pairs, each having its elements in order

    if (a <= b) {
        temp1 = (struct pair) { a, b };
    } else {
        temp1 = (struct pair) { b, a };
    }

    if (c <= d) {
        temp2 = (struct pair) { c, d };
    } else {
        temp2 = (struct pair) { d, c };
    }

    // order the two pairs by their first elements

    if (temp1.x <= temp2.x) {
        pair1 = temp1;
        pair2 = temp2;
    } else {
        pair1 = temp2;
        pair2 = temp1;
    }

    /*
     * These mathematical relationships now hold:
     *
     *     pair1.x <= pair1.y
     *     pair1.x <= pair2.x <= pair2.y
     *
     * The order of e relative to the others determines how we proceed.
     */

    if (pair1.y <= e) {
        // pair1.x <= pair1.y <= e; pair1.x <= pair2.x <= pair2.y
        if (pair2.x < pair1.y) {
            // pair1.x <= pair2.x < pair1.y <= e; pair2.x <= pair2.y
            // return the lesser of pair1.y and pair2.y
            return (pair1.y <= pair2.y) ? pair1.y : pair2.y;
        } else {
            // pair1.x <= pair1.y < e, pair2.x;  pair2.x <= pair2.y
            // return the lesser of e and pair2.x
            return (e <= pair2.x) ? e : pair2.x;
        }
    } else {
        // pair1.x, e <= pair1.y; pair1.x <= pair2.x <= pair2.y
        if (pair2.x <= e) {
            // pair1.x <= pair2.x <= e <= pair1.y; pair2.x <= pair2.y
            // return the lesser of e and pair2.y
            return (e <= pair2.y) ? e : pair2.y;
        } else {
            // pair1.x, e <= pair1.y, pair2.x; pair2.x <= pair2.y
            // return the lesser of pair1.y and pair2.x
            return (pair1.y <= pair2.x) ? pair1.y : pair2.x;
        }
    }
}

That can of course be adapted for input in the form of an array instead of five individual values.

The six-level "full decision tree" version is not something I really want to contemplate writing.

score 0 · Answer 2 · answered Jun 05 '22 at 15:02

0

Use an array, not a set of variables.
Then Sort the Array
Then take the middle of the array.

#include <stdio.h>
#include <stdlib.h>

#define COUNT_OF(x) ((sizeof(x)/sizeof(0[x])) / ((size_t)(!(sizeof(x) % sizeof(0[x])))))

int cmp(void* a, void* b)
{
    return *(int*)b - *(int*)a;
}

int main()
{
    int num[5];
    printf("Enter %d numbers\n", COUNT_OF(num));
    for(int i=0; i<COUNT_OF(num); ++i)
    {
        scanf("%d",&num[i]);
    }
    
    qsort(num, COUNT_OF(num), sizeof(int), cmp);
    
    printf("Middle value at index %d is %d\n", COUNT_OF(num)/2, num[COUNT_OF(num)/2]);
    
    return 0;
}

answered Jun 05 '22 at 15:02

abelenky

63,815
23
109
159

1

why use that long COUNT_OF rather then `#define COUNT_OF(X) (sizeof(X)/sizeof(*X))`?? – Tomer W Jun 05 '22 at 15:04
Fully explained at: https://stackoverflow.com/questions/1598773/is-there-a-standard-function-in-c-that-would-return-the-length-of-an-array/1598827#1598827 but the basic point is the long version will catch mistakes where you accidentally pass a non-array type. – abelenky Jun 05 '22 at 15:11

Finding the middle number of five integer numbers

2 Answers2