Determine the three maximum and two minimum values of the array-CodePudding

Task: Given a natural number N (set arbitrarily as a preprocessor constant) and one-dimensional array A0, A1, …, AN-1 of integers (generate positive and negative elements randomly, using the <stdlib.h> library function rand()). Perform the following actions: Determine the three maximum and two minimum values of this array.

Code with search for two minimum values:

#include <stdio.h>
#include <stdlib.h>
#define N 9
int main()
{
    int M[N], i, a[N], fbig, sbig, tbig, min, smin;
    for(i = 0; i < N; i  )
    {
        M[i] = rand() % 20 - 10;
        printf("%i\t", M[i]);
    }
    printf("\n");
    for(i = 0; i < N; i  )
    {
        if(a[i]<min)
        {
            smin=min;
            min=a[i];
        }
        else
            if(a[i]<smin && a[i]!=min)
                smin=a[1];
    }            
    printf("\nMinimum=%d \nSecond Minimum=%d",min,smin);
    
return 0;
}

I tried to compare array elements with each other but here is my result:

-7 -4 7 5 3 5 -4 2 -1

Minimum=0 Second Minimum=0

I would be very grateful if you could help me fix my code or maybe I'm doing everything wrong and you know how to do it right. Thank you for your time

CodePudding user response：

The easiest solution would be to sort the input array. The minimum is the first 2 values and the maximum would be the last 3:

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

#define MAX_N 3
#define MIN_N 2
#define N 9

void generate(size_t n, int a[n]) {
    for(size_t i = 0; i < n; i  )
        a[i] = rand() % 20 - 10;
}

void print(size_t n, int a[n]) {
    for(size_t i = 0; i < n - 1; i  )
        printf("%d, ", a[i]);
    if(n) printf("%d\n", a[n-1]);
}

int cmp_asc(const void *a, const void *b) {
    if(*(int *) a < *(int *) b) return -1;
    if(*(int *) a > *(int *) b) return 1;
    return 0;
}

int main() {
    int t = time(0);
    srand(t);
    printf("%d\n", t); // essential for debugging

    int a[N];
    generate(N, a);
    print(N, a);

    qsort(a, N, sizeof *a, cmp_asc);
    print(MIN_N, a);
    print(MAX_N, a   (N - MAX_N));
}

If you cannot use sort then consider the following purpose built algorithm. It's much easier to use arrays (min and max) rather than individual values, and as a bonus this allows you to easily change how many minimum (MIN_N) and maximum (MAX_N) values you want. First we need to initialize the min and max arrays, and I use the initial values of the input array for that. I used a single loop for that. To maintain the invariant that the min array has the MIN_N smallest numbers we have seen so far (a[0] through a[i-1]) we have to replace() largest (extrema) of them if the new value a[i] is smaller. For example, if the array is min = { 1, 10 } and the value we are looking at is a[i] = 5 then we have to replace the 10 not the 1.

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

#define MAX_N 3
#define MIN_N 2
#define N 9

void generate(size_t n, int a[n]) {
    for(size_t i = 0; i < n; i  )
        a[i] = rand() % 20 - 10;
}

void print(size_t n, int a[n]) {
    for(size_t i = 0; i < n - 1; i  )
        printf("%d, ", a[i]);
    if(n) printf("%d\n", a[n-1]);
}

int cmp_asc(const void *a, const void *b) {
    if(*(int *) a < *(int *) b) return -1;
    if(*(int *) a > *(int *) b) return 1;
    return 0;
}

int cmp_desc(const void *a, const void *b) {
    return cmp_asc(b, a);
}

void replace(size_t n, int a[n], int v, int (*cmp)(const void *, const void *)) {
    int *extrema = &a[0];
    for(size_t i = 1; i < n; i  ) {
        if(cmp(extrema, &a[i]) < 0) {
            extrema = &a[i];
        }
    }
    if(cmp(extrema, &v) > 0)
        *extrema = v;
}

void min_max(size_t n, int a[n], size_t min_n, int min[n], size_t max_n, int max[n]) {
    for(size_t i = 1; i < n; i  ) {
        if(i < min_n)
            min[i] = a[i];
        else
            replace(min_n, min, a[i], cmp_asc);
        if(i < max_n)
            max[i] = a[i];
        else
            replace(max_n, max, a[i], cmp_desc);
    }
}

int main() {
    int t = time(0);
    srand(t);
    printf("%d\n", t); // essential for debugging

    int a[N];
    generate(N, a);
    print(N, a);

    int min[MIN_N];
    int max[MAX_N];
    min_max(N, a, MIN_N, min, MAX_N, max);
    print(MIN_N, min);
    print(MAX_N, max);
}

and here is example output. The first value is a the seed in case you have to reproduce a run later. Followed by input, min and max values:

1674335494
-7, 0, -2, 7, -3, 4, 5, -8, -9
-9, -8
7, 5, 4

If MIN_N or MAX_N gets large, say, ~1,000 , then you want sort the min and max arrays and use binary search to figure out where to inserta[i]. Or use a priority queue like a heap instead of arrays.

CodePudding user response：

As already noted, the most direct way to do this would be to simply sort the array. (In fact, if all you need is an output of five integers then your array only need be five elements long.) But I will presume that that is not the point of this homework.

^{Your goal isn’t super efficiency or a pretty algorithm. It is simply to solve the tasks. Do them one at a time.}

First question: How would you find the largest value?

Answer: Loop through the array, keeping track of the largest element found so far.

int largest = array[0];  // why start with this value?
for (int n = 1;  n < size;  n  )
  if (array[n] > largest)
    largest = array[n];

Second question: How would you find the smallest value?

Almost the same way, with only a single change: Instead of testing if (array[n] > largest) we want to test if (array[n] < smallest), right?

Third question: How would you find the second smallest value?

It should not surprise you that you just need to change the if condition in that loop again. An element would be the second smallest if:
• it is the smallest value greater than the smallest.
Think about how you would change your condition:

int second_smallest = largest;  // why start with this value?
for (int n = 0;  n < size;  n  )
  if (...)                      // what is the new test condition?
    second_smallest = array[n];

Fourth question: can you write another loop to find the second-largest? How about the third-largest?

Further considerations:

Is it possible that the third-largest is the same as the second-smallest?
Or the smallest?
Is it possible for there to not be a third-largest?
Does it matter?

Put all these loops together in your main() and print out the results each time and you are all done!

...
int main(void)
{
  int array[SIZE];
  // fill array with random numbers here //

  int largest = array[0];
  for (...)
    if (...)
      ...

  int smallest = largest;
  for (...)
    if (...)
      ...

  int second_smallest = largest;
  for (...)
    if (...)
      ...

  int second_largest = smallest;
  for (...)
    if (...)
      ...

  int third_largest = smallest;
  for (...)
    if (...)
      ...

  printf( "The original array = " );
  // print original array here, then: //
  printf( "largest      = %d\n", largest );
  printf( "2nd largest  = %d\n", second_largest );
  printf( "3nd largest  = %d\n", third_largest );
  printf( "2nd smallest = %d\n", second_smallest );
  printf( "smallest     = %d\n", smallest );
  return 0;
}

Bonus: be careful with variable names. There has been no need to use short abbreviations since before the early nineties. Prefer clarity over brevity.