Most efficient way to get the largest 3 elements of an array

Question

I have been given an array of elements and an inbuilt function which can sort 5 elements at a time. How do I use only this function to obtain the largest 3 elements of the array with the least number of calls to this function?

The approach I have tried is dividing the array in groups of 5 each, applying the function on each group, and applying the function on the maximums obtained from each group.

This approach fails when the highest and second highest happen to be present in the same group. Is there a better approach to do this?

Answer 1

Since you have the built-in method to sort five elements I suggest: Sort the first five elements from the array. Repeatedly discard the two smallest of the five and replace with two more elements from the array (two elements that have not yet been considered), then sort the five again. In the end take the largest three of the five.

It will be possible to do a bit better than what I have sketched. Say you have 25 elements. For each group of 5 find the three largest. Then among the nos. 1 from each group find the three largest. The same for the nos. 2 from each group and the nos. 3. Now we can deduce that the three largest overall will be among the three largest nos. 1, the two largest nos. 2 and the single largest no. 3, that is six elements instead of 9. So we can find the three largest in just two more calls to your built-in method instead of three more calls. Generalizing the idea to any size of the original array will be complicated, though.

Answer 2

How about this method.

1. Divide the array into groups of 5
2. Apply the provided sort method for each group of 5 elements
3. Get the first 3 elements from each array
4. Then merge the identified 3 elements in each group to one single array
5. Now repeat from step 1 to 4, until the final array size is less than or equal to 5
6. Get the first 3 elements from the final array

Answer 3

#include <iostream>


void sortThree(int res[3]) {
   for(int j = 0; j < 2; j++) {
      if(res[j] > res[j+1])
         std::swap(res[j], res[j+1]);
}
   if(res[0] > res[1]) std::swap(res[0], res[1]); // second pass
}

bool lsearch(int src[], int n, int k) {
  for(int i = 0; i < n; i++) {
    if(src[i] == k) return true;
  }
  return false;
}

void getThreeLargest(int arr[], int n, int res[3]) {
  res[0] = arr[0];
  res[1] = arr[1];
  res[2] = arr[2];
  sortThree(res);
  for(int i = 3; i < n; i++) {
    // if no repetition wanted
    // if(arr[i] > res[0] && !lsearch(res, 3, arr[i])) {
    if(arr[i] > res[0]) {
      res[0] = arr[i];
      sortThree(res);
    }
  }
}

int main(int argc, char *argv[])
{
  int arr[] = {91,21,3,-4,5,2,1,90,9,11};
  int res[3];
  getThreeLargest(arr, 10, res);
  for(int i = 0; i < 3; i++)
    std::cout << res[i] << '\n';
  return 0;
}

Very simple solution here in a c-way to do it. You can easily convert it to java. Scanning the array is O(n). Since the little array to be sorted and searched has only 3 elements we can easily use linear search to avoid repetition and sorting takes only 2 comparisons. It's still O(n).

Answer 4

#include<stdio.h>
#include<limits.h>

int retmax(int *a,int n,int exc){

    int max = INT_MIN;
    for(int i=0;i<n;i++){
        if(a[i] > max && a[i] < exc)
           max = a[i];
    }

    return max;
}

int main(){

    int a[]={32,54,12,43,98,45,87};
    int size = sizeof(a)/sizeof(a[0]);

    int x = retmax(a,size,INT_MAX);
    int y = retmax(a,size,x);
    int z = retmax(a,size,y);

    printf("%d %d %d",x,y,z);
}

A simple O(n) solution.