-1
\$\begingroup\$

I am completing a simple but tedious program in C++. I have a function that must find the minimum value in an array. Here is the code:

double min(double x[], int total)
{
    for (int i = 0; i < total; i++)
    {
        x[0] = (x[i] < x[0]) ? x[i] : x[0];
    }
    return x[0];
}

And a different approach, using a nested for loop and an if statement inside:

double min(double x[], int total)
{
    for (int i = 0; i < total; i++)
    {
        for (int j = i + 1; j < total; j++)
        {
            if (x[j] > x[i])
            {
                double temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
        }
    }
    return x[0];
}

I have a few questions here:

  1. Is the first code really any more efficient than the second? I'm sure that as the array grows then time complexity will too 0(n). So maybe with arrays this is better?
  2. Is there any other way that I could improve this further? I'm sure it would be far more efficient to use a library, I just don't know many C++ libraries.

Assuming that the data is not needed after this function call, how much more practical would my first option be? Would it only make a noticeable difference where num_elements > 10000?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ For all new users when you down vote a question, please add a comment explaining what is wrong with the question. Down voting without commenting is somewhat rude and doesn't help the person that asked the question improve the question. It is not clear why this question has 3 down votes. \$\endgroup\$ – pacmaninbw Nov 4 '20 at 14:40
  • \$\begingroup\$ @TobySpeight Welcome back, missed you these last few months. \$\endgroup\$ – pacmaninbw Nov 4 '20 at 17:18
  • \$\begingroup\$ Thanks @pacmaninbw. Was unexpectedly out of the office for a few weeks. :-( I have equipment at home now and catching up; lots of comments to answer! \$\endgroup\$ – Toby Speight Nov 4 '20 at 17:20
6
\$\begingroup\$
  • The biggest issue I see with this code, is that it destroys data. It does not return the min--it OVERWRITES the first array value with the min, and then returns the min. You should try to write correct code before writing fast code.
  • Rename 'total' to 'num_elements' or something. 'total' sounds like it's the sum of the values.
  1. I don't know what you mean by your suggestion around a "nested for loop". Include code if you want an opinion about that. An if-statement inside a for-loop, is not called a "nested for loop". A "nested for loop" means a for-loop inside a for-loop.

    This is the same efficiency as an if statement. The ternary operator and an if statement will compile to the same thing. A ternary operator only affects readability.

  2. You could use std::min. https://en.cppreference.com/w/cpp/algorithm/min

\$\endgroup\$
4
  • \$\begingroup\$ The std::min suggestion is very good. If the OP stays with their loop they should use iterators and can use a ranged for loop as well. \$\endgroup\$ – pacmaninbw Nov 4 '20 at 1:23
  • \$\begingroup\$ I can edit my post to be more specific, but when I say nested for loop and if statement, I mean for (int i = 0; ...) {for (int j = i + 1; ...) { if (x[i] < x[j] ) { //temp variable... }}}. And this is all assuming that the array can be destroyed and won't be needed after the function. \$\endgroup\$ – stupidQuestions Nov 4 '20 at 1:40
  • 2
    \$\begingroup\$ That explains a lot. The second example sorts the list (using bubble sort, which you should not do--use std::sort if you ever need to sort something). Just finding a minimum is more efficient than sorting a list, yes. As a rule of thumb, the number of nested loops and the efficiency are almost the same, as long as you're not accessing files or the internet, etc. \$\endgroup\$ – Zachary Vance Nov 4 '20 at 1:47
  • \$\begingroup\$ Thanks, I learned a lot. (Avoid bubble sort because of 0(n^2)). \$\endgroup\$ – stupidQuestions Nov 4 '20 at 17:29
4
\$\begingroup\$

Depends on what you're trying to do.

The STL Algorithm library has std::min which will give you the result; you'll still need to compare every item though, and that achieves O(N) time complexity.

#include <algorithm>
double min(double x[], int total){ // There's a subtle chance for bugs right here
    ASSERT(total >= 1); // An ugly fix
    auto res = x[0];
    for (int i = 1; i < total; i++)
        res = std::min(res, x[i]);
    return res;
}

then there's the STL algorithm min_element which returns an iterator to the smallest element. As it's a full blown function, you don't need to declare your own. It too, is a O(N) algorithm.

#include <algorithm>

int main(){
double x[total]; // total defined elsewhere, maybe as macro or constexpr
// Your code
auto min_number = *std::min_element(std::cbegin(x),std::cend(x));
//more code

Sorting the array won't provide you with a speedup, because unless the array is already sorted, then the Average Time Complexity will be O(N * log(N)), and a worst case O(N²).

As a final note: if you use the first method, like in your code, you're opening yourself up to issues where total could be zero or negative, giving your access issues.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ In the last case, prefer std::begin(x) and std::end(x), as &x[size] is only really applicable to native arrays, and has too many moving parts. \$\endgroup\$ – Deduplicator Nov 4 '20 at 13:42
  • \$\begingroup\$ True, given the initial state of the question, I was under the impression that OP might be passing c-arrays around instead of standard containers. \$\endgroup\$ – Alex Shirley Nov 4 '20 at 13:51
  • \$\begingroup\$ Thanks for the answer. It helps. \$\endgroup\$ – stupidQuestions Nov 4 '20 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.