Sum the largest five numbers

Question

I'm doing a code-challenge problem:

---

Input

The first line consists of an integer T (T ≤ 100) which represents the number of test cases. Each test case consists of an integer N (5 ≤ N ≤ 100.000) which represents the number of integers, followed by a line that consists of N integers Ai (0 ≤ Ai ≤ 1000) separated by a space.

Output

For each test case, print in a line an integer that represents the sum of 5 largest numbers.

---

My code (below) works for small tests, but on the online judge, it resulted in Time Limit Exceeded. Some approaches I've tried that I think speed up the program (need confirmation):

1. Changing language from C++ to C (does it give significant boost?)
2. When calculating the sum, I use while instead of for loop (which one is more effective?)

---

#include <stdio.h>
int main () {
 int testCases;
 scanf("%d", &testCases);
 
 for (int i = 1; i <= testCases; i++) {
 int size, sum, temp, k, limit;
 sum = 0;
 temp = 0;
 scanf("%d", &size);
 
 int array[size];
 
 for (int i = 0; i < size; i++) {
 scanf("%d", &array[i]);
 }
 
 for (int i = 0; i < size; i++) {
 for (int j = i+1; j < size; j++) {
 if (array[j] < array[i]) {
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;
 } else {
 continue;
 }
 }
 }
 
 k = size - 1;
 limit = size - 6;
 
 while (k > limit) {
 sum += array[k];
 k--;
 }
 
 printf("%d\n", sum);
 } 
}

• L. F.: Interestingly, the code is neither a well-formed C++ program nor a well-formed C program because of the usage of VLAs (variable length arrays).

Answer 1

1. NO: C++ is not magically slower than C. Bad C++ code is slower than good C code and vice versa.

2. NO: For the compiler it is completely irrelevant whether you use a for or a while loop as they will all be normalized into a consistent representation anyway.

Now to the actual review. Your code will not improve from porting to C as you are already not using any C++ features.

In C++ you should generally use streams. They have a bad reputation but generally they greatly improve your code:

int numTests;
std::cin >> numTests;

This also works for ranges

std::vector<int> array(size);
std::istream_iterator<int> eos; // end-of-stream iterator
std::istream_iterator<int> iit (std::cin); // stdin iterator
std::copy(iit, eos, array.begin()); // copy from std::cin

For sorting you should refer to the standard library aka std::sort. However, you should not even sort but determine the 5 largest elements. This is achieved by the algorithm nth_element

std::nth_element(array.begin(), std::next(array.begin(), 5), array.end(), std::greater<int>());

Now you can simply sum them up

const int result = std::accumulate(array.begin(), std::next(array.begin(), 5), 0);

So the whole algorithm would be

const int sum_largest(const std::size_t numElements, std::vector<int>& data) {
 if (numElements > data.size()) {
 // Error handling
 }
 std::nth_element(data.begin(), std::next(data.begin(), numElements), data.end(), std::greater<int>());
 return std::accumulate(data.begin(), std::next(data.begin(), numElements), 0);
}

• Toby Speight: Oh, one other point - just as the question code should check the return value from scanf(), code using operator >> should check the consequent state of the stream before assuming that the read was successful.
• miscco: @TobySpeight You are absolutely correct that input code should check the state. (Allthough for coding challenges one can work with the guaranteed input)
• L. F.: Why return a const int? Here const hardly makes a difference as the return type of a function per [expr.6].
• miscco: @L.F. Because copy & paste is strong. That was a leftover from the line before.
• ALX23z: For getting 5 largest elements it is better to use std::partial_sort or std::partial_sort_copy. It is implemented via a different algorithm which is faster for small numbers like 5 (but slower for large numbers).

Answer 2

We need only 5 maximum elements, for that we don't need to sort whole array. We can use alternative approach

Approach 1: Use 5 local variables and keep track of minimum element in it.

Approach 2: Use Min-heap and insert first 5 elements of array in min-heap, then iterate on array from index = 5, if heap-root is smaller than number in array then extract that number from min-heap, and insert new.

• L. F.: Welcome to Code Review!

Answer 3

There isn't going to be a significant difference between C and C++ when using the same algorithm.

Using a while loop versus a for loop in this case will not have a significant difference either. The loop is only going to sum 5 values.

The problem is the algorithm, as another answer pointed out do as much of the sorting as possible as the numbers are input. Don't input directly into the array, because that forces the sort, input into a variable and compare the variable against the the contents of the already sorted array, only replace the numbers in the array if the new number is larger.

If the program was broken up into functions you could profile it to see where it was spending the most time, but it is obvious that the sort is the time sink. Breaking it up into function might help with writing the code and debugging as well.