Most efficient way to get the largest 3 elements of an array using no comparisons but a procedure for ordering 5 elements descendantly

Question

I have been given an array of elements and a 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

#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).