Determine the three maximum and two minimum values of the array

Question

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

Answer 1

I will revise my answer if op address what to do about duplicate values. My answer assume you want possible duplicate values in the minimum and maximum arrays, while other answers assume you want unique values.

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.

Answer 2

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 = 0;  n < size;  n++)
  if (array[n] > largest)
    largest = array[n];

---

Second question: How would you find the smallest value?

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

int smallest = largest;  // why start with this value?
for (int n = 0;  n < size;  n++)
  if (...)               // new condition goes here
    smallest = array[n];

---

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

Answer: 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];

^{Remember, this time you are testing two things, so your test condition needs that && in it.}

---

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

At this point you should be able to see the variation on a theme and be able to write a loop that will get you any N^th largest or smallest value, as long as you already have the (N-1)^th to work against.

---

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

Example outputs:

{ 1 2 3 4 }
smallest     = 1
2nd smallest = 2
3rd largest  = 2
2nd largest  = 3
largest      = 4

{ 5 5 5 5 5 }
smallest     = 5
2nd smallest = 5
3rd smallest = 5
largest      = 5

{ 1 2 }
smallest     = 1
2nd smallest = 2
3rd smallest = 2
largest      = 2

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

Answer 3

There are multiple problems in your code:

• min and smin are uninitialized, hence the comparisons in the loop have undefined behavior and the code does work at all. You could initialize min as a[0] but initializing smin is not so simple.

• there is a typo in smin = a[1]; you probably meant smin = a[i];

Note that the assignment is somewhat ambiguous: are the maximum and minimum values supposed to be distinct values, as the wording implies, or should you determine the minimum and maximum elements of the sorted array?

• For the latter, sorting the array, either fully or partially, is a simple solution.

• For the former, sorting is also a solution but further testing will be needed to remove duplicates from the sorted set.

Here is a modified version to print the smallest and largest values:

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

#define N      9
#define N_MIN  2
#define N_MAX  3

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int a[N], i, j, e, dup;
    int smallest[N_MIN], nsmall = 0;
    int largest[N_MAX], nlarge = 0;

    srand(time(NULL));

    for (i = 0; i < N; i++) {
        a[i] = rand() % 20 - 10;
        printf("%i\t", a[i]);
    }
    printf("\n");
    for (i = 0; i < N; i++) {
        e = a[i];
        dup = 0;
        for (j = 0; j < nsmall; j++) {
            if (e == smallest[j]) {
                dup = 1;
                break;
            }
            if (e < smallest[j]) {
                swap(&e, &smallest[j]);
            }
        }
        if (!dup && nsmall < N_MIN) {
            smallest[nsmall++] = e;
        }
        e = a[i];
        dup = 0;
        for (j = 0; j < nlarge; j++) {
            if (e == largest[j]) {
                dup = 1;
                break;
            }
            if (e > largest[j]) {
                swap(&e, &largest[j]);
            }
        }
        if (!dup && nlarge < N_MAX) {
            largest[nlarge++] = e;
        }
    }
    printf("smallest values: ");
    for (i = 0; i < nsmall; i++) {
        printf(" %d", smallest[i]);
    }
    printf("\n");
    printf("largest values: ");
    for (i = nlarge; i --> 0;) {
        printf(" %d", largest[i]);
    }
    printf("\n");
    return 0;
}