-1

I have two pieces of code for finding the three largest numbers in a given array. The first one uses std::sort to sort an array of three elements each time it finds a number larger than the current smallest of the three. The second one performs manual sorting using if statements to maintain the order after a larger number is found.

Is there a significant difference in terms of efficiency between these two methods? Given the fact that the std::sort function is designed for sorting collections of arbitrary size, and the size of the array in this case is always small (3 elements), would the manual sorting be more efficient than using std::sort?

I understand that the overall time complexity of both functions is O(n), where n is the size of the input array, but I'm wondering about the efficiency of the sorting operation itself.

Here are the two versions of the code:

#include <vector>
std::vector<int> findThreeLargestNumbers(const std::vector<int>& array) {
    constexpr int COUNT {3};
    std::vector<int> maxArray{ array.begin(),array.begin()+COUNT};
    std::sort(maxArray.begin(), maxArray.end());
    for (int i = COUNT; i < array.size(); ++i)
    {
        if (array[i] > maxArray[0])
        {
          maxArray[0] = array[i];
          std::sort(maxArray.begin(), maxArray.end());
        }
    }
   
    return maxArray;
}


#include <vector>
std::vector<int> findThreeLargestNumbers(const std::vector<int>& array) {
    constexpr int COUNT{ 3 };
    std::vector<int> maxArray{ array.begin(),array.begin() + COUNT };
    std::sort(maxArray.begin(), maxArray.end());
    for (int i = COUNT; i < array.size(); ++i)
    {
        if (array[i] > maxArray[0])
        {
             maxArray[0] = array[i];
            if (maxArray[0] > maxArray[1])
            {
                swap(maxArray[0], maxArray[1]);
            }
            if (maxArray[1] > maxArray[2])
            {
                swap(maxArray[1], maxArray[2]);
            }
        }
    }

    return maxArray;
}
Sami
  • 513
  • 4
  • 11
  • 4
    Have you tried to measure or have you looked at the generated code? (e.g. on godbolt.org) My hot guess is that they will perform the same. – chrysante Jul 20 '23 at 20:41
  • 1
    Also you might be interested in [this answer](https://stackoverflow.com/a/7272702/21285803) – chrysante Jul 20 '23 at 20:44
  • 3
    Depends on the implementation of `std::sort`. The only way to find out is to benchmark it. Most implementations will switch to a different algorithm to sort the last few elements – Alan Birtles Jul 20 '23 at 20:53
  • 2
    `std::partial_sort()` is designed for the task. – Eugene Jul 20 '23 at 20:54
  • 1
    I suggest using [`std::nth_element`](https://en.cppreference.com/w/cpp/algorithm/nth_element) instead of `std::sort`. [Example](https://godbolt.org/z/a71a4vb9e) – Ted Lyngmo Jul 20 '23 at 20:56
  • 1
    Does it matter for your app? Unless it's doing the sort millions of times the answer is probably that it makes no difference all all even if one takes 10 times as long. – Dave S Jul 20 '23 at 21:06
  • @TedLyngmo `std::nth_element` is efficient for finding a middle element. Don't use to find 5 maximal elements or the like. – ALX23z Jul 20 '23 at 21:06
  • 1
    @ALX23z All elements before the nth element will be just as big or bigger than the nth element. It's much like a `partial_sort` except the elements are not sorted, so it should be cheaper than a `partial_sort` to get the 3 largest elements. – Ted Lyngmo Jul 20 '23 at 21:16
  • The search term is "quick select" – Aykhan Hagverdili Jul 20 '23 at 21:48
  • I agree with Ted, a single call to `nth_element` will replace all the looping and sorting. Only his claim "All elements before the nth element will be just as big or bigger than the nth element" is backwards. It partitions into the smallest `N` and largest `.size()-N+1` (with the Nth straddling both partitions) so choose N = `.size() - 2` – Ben Voigt Jul 20 '23 at 23:01
  • @TedLyngmo you think with algo description, not in how they achieve it. partial_sort and nth_element achieve it very differently. `nth_element` uses quick-sort like steps taking O(n log n). There was a talk about performance comparison with various algos where their best uses were discussed. – ALX23z Jul 20 '23 at 23:39
  • @BenVoigt I made it backwards because the question asked for the 3 greatest. `std::nth_element(std::begin(arr), std::next(std::begin(arr), 2), std::end(arr), std::greater{});` – Ted Lyngmo Jul 21 '23 at 03:15
  • @ALX23z Indeed, you seem to be correct: when it's a matter of getting very few elements, like 3 in this case: [QuickBench](https://quick-bench.com/q/bRb7u-psYfUsIRlcnFG2tykeGmM). For 5, they seem equally fast and the more elements you want to find makes `nth_element` more and more useful. – Ted Lyngmo Jul 21 '23 at 04:16
  • @TedLyngmo: Changing the comparison to `std::greater` indeed flips the rules, but your earlier comment didn't specify that. – Ben Voigt Jul 21 '23 at 14:00
  • @BenVoigt Aha, true. My earlier comment was a continuation of my even earlier comment. It was a link to compiler explorer though, so, the connection was a bit lost. Sorry. – Ted Lyngmo Jul 21 '23 at 14:07

1 Answers1

1

Which is faster will depend on the implementation of std::sort you are using, but for typical implementations we can expect the running times to be about the same -- because typical implementations of std::sort treat very short input ranges as special cases.

jwezorek
  • 8,592
  • 1
  • 29
  • 46