Most efficient way to find iterators of 4 maximum values in const vector in C++

I have to find 4 the biggest numbers in a const vector and return their positions. I want this code to have the best time and space complexity. My first idea is to copy this const vector into vector and bubble sort it 4 times. That gives me 4*N but i have to create a vector. Second idea is to put everything from this const vector into priority_queue. That gives me a N*log2(N) time complexity without creating another variables. The maximum of N is around 100.

Is there any other options to do it in the fastest and the least space-consuming way?

EDIT: It doesn't matter which one is the biggest, I just need to return position of this 4 items in the input vector.

Solution

You can implement this quite easily with an extra vector, and the nth_element algorithm, which is O(n) time:

std::vector<int> const v = ...;

// create a vector of elements with original indexes
std::vector<std::pair<int,int>> res;

// populate the result vector
int k = 0;
for (int i : v)
  res.push_back({i,k++});

// find the maximum 4 elements
std::nth_element(res.begin(), res.begin() + 4, res.end(),
   [](auto const &a, auto const &b) { return a.first > b.first; });

Here's a demo.

Note that this solution uses O(n) extra space. If N grows large, then this might not be the right approach for finding just 4 largest elements. It's still a good approach if you want the M largest elements, where M grows like N.