Finding the middle number of five integer numbers-CodePudding

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

CodePudding user response：

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

CodePudding user response：

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.

CodePudding user response：

Not comparison-optimal, but probably decently fast, here is a pseudocode:

int R[]= { 0, 0, 0, 0, 0 };
R[n1<n2 ? 1 : 2]  ; R[n1<n3 ? 1 : 3]  ; R[n1<n4 ? 1 : 4]  ; R[n1<n5 ? 1 : 5]  ;
R[n2<n3 ? 2 : 3]  ; R[n2<n4 ? 2 : 4]  ; R[n2<n5 ? 2 : 5]  ;
R[n3<n4 ? 3 : 4]  ; R[n3<n5 ? 3 : 5]  ;
R[n4<n5 ? 4 : 5]  ;

tells you the ranks of all five elements in 10 comparisons. The median is the element with rank 2.