7
\$\begingroup\$

Here's my implementation using divide and conquer in C++.

What do you think of this implementation regarding running time ?

#include <iostream>
#include <tuple>
using namespace std;

tuple <int,int> largest_two_numbers(int *arr,int size)
{
    //The algorithm is based on returning a tuple with the largest two numbers in the array

    if (size==1)
        return tuple<int,int>(arr[0],arr[0]);
    if (size==2)
        return tuple<int,int>(arr[0],arr[1]);

    //Split the arr into two arrays
    int arr_1[size/2],arr_2[size/2+(size&1)];
    for (int i = 0; i < size/2; ++i)
    {
        arr_1[i]=arr[i];
        arr_2[i]=arr[i+size/2];
    }
    if (size&1) arr_2[size/2]=arr[size-1];

    //Return two tuples one for the right half and the other for the left
    tuple <int,int> right= largest_two_numbers(arr_1,size/2);
    tuple <int,int> left = largest_two_numbers(arr_2,size/2+(size&1));

    //Declare an array maxis with the values inside the two tuples combined and find the largest two numbers
    int maxis[]={get<0>(right),get<1>(right),get<0>(left),get<1>(left)};
    int max1=maxis[0],max2=maxis[0];
    for (int i = 0; i < 4; ++i)
    {
        if (maxis[i]>max1) max1=maxis[i];
    }
    for (int i = 0; i < 4; ++i)
    {
        if (maxis[i]>max2 && maxis[i]<max1) max2=maxis[i];
    }

    //Return a tuple with the largest two numbers
    return tuple<int,int>(max1,max2);
}

int main(){
    int arr[]={-1,98,22,1,0,301,112},n=7;

    //Print the second largest element in the array which is the second element in the tupple
    cout << get<1>(largest_two_numbers(arr,n));
}
\$\endgroup\$
  • 2
    \$\begingroup\$ This is not standard c++ due to the use of VLA. I'm not a fan of using namespace std, although it's fine for trivial programs. This uses a ton of extra memory for no real benefit. I'm pretty sure it is still technically O(N), but it has a pretty big constant as it makes 8 comparisons in the merge. A simple for loop which would make at most 2(N-1) comparisons. \$\endgroup\$ – Kenny Ostrom Dec 16 '17 at 20:44
  • \$\begingroup\$ @KennyOstrom, why -1? \$\endgroup\$ – Incomputable Dec 16 '17 at 20:45
  • \$\begingroup\$ You don't have anything to compare the first number to. Not that it matters, lower order term. \$\endgroup\$ – Kenny Ostrom Dec 16 '17 at 20:46
  • \$\begingroup\$ @KennyOstrom I thought it was theta(8*log_2(n)), in each division we only combine 4 values together in an array and loop twice thus having 8 operations per division step ? \$\endgroup\$ – Ahmed Karaman Dec 16 '17 at 20:48
  • \$\begingroup\$ two subproblems of size n/2, they balance out. The merge is constant, so irrelevant, the work is in the leaves: theta (n ^ log base 2 of 2) = theta(n^1) = theta(n). \$\endgroup\$ – Kenny Ostrom Dec 16 '17 at 21:08
7
\$\begingroup\$

Inefficient algorithm

As stated in the comments, the algorithm is actually pretty convoluted. One cannot find the maximum without looking at all of the elements, if they don't have any idea about the pattern of the input.

On top of that, it allocates quite a lot of memory.

Non-standard C++

VLA (variable length array) is not part of C++. It might be an extension in your compiler

Using C++ as C

The code is extremely imperative. It has a lot of control that it doesn't use, and doesn't have any benefit over standard algorithms. It is also bound to int arrays, to pointers, in fact. May be as C code it would be ok (if algorithm problems are fixed), but this is not effective usage of C++ features.

Benchmarking

Usually when seriously talking about performance people also use benchmarks. Having some real statistics on multiple platforms will strengthen your argument.

Alternative approach

Now that we know that we need to pass through anyway, lets write simple loop over the whole range:

#include <functional>
#include <array>
#include <utility>

template <typename ForwardIterator, typename Compare = std::less<>>
std::array<ForwardIterator, 2> find_2greatest(ForwardIterator first, 
                                              ForwardIterator last,
                                              Compare cmp = {})
{
    if (first == last)
    {
        return {first, first};    
    }

    auto greatest = first;
    auto runner_up = greatest;

    for (++first; first != last; ++first)
    {
        if (cmp(*runner_up, *first))
        {
            runner_up = first;   
            if (cmp(*greatest, *runner_up))
            {
                std::swap(greatest, runner_up);   
            }
        }
    }

    return {greatest, runner_up};
}

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v{1, 1, 2, 3, 4, 5, 6};

    auto greatest2 = find_2greatest(std::begin(v), std::end(v));

    std::cout << "the greatest: " << *greatest2.front() << '\n'
              << "second greatest: " << *greatest2.back() << '\n';
}

The code doesn't return the objects themselves. They might be non-copyable, or user might want only the location of those elements. In general, C++ search algorithms usually return iterators. Also it is not bound to only vectors or ints, it can work on anything that allows multiple passed over the range. Your naming might be better than mine though.

\$\endgroup\$
  • 1
    \$\begingroup\$ Not a big deal, but I would compare to greatest2 first. It is more likely to shortcut the next comparison, and I prefer using if ... else over continue. Also that while look looks a lot like an expanded for loop. \$\endgroup\$ – Kenny Ostrom Dec 16 '17 at 22:30
  • \$\begingroup\$ @KennyOstrom, I’m going to sleep, but the second point is pretty legit. I’ll fix it tomorrow, but if you want you can edit it now. The first point makes assumptions about input pattern :) \$\endgroup\$ – Incomputable Dec 16 '17 at 22:34
  • \$\begingroup\$ @KennyOstrom, fixed. Now it looks a lot nicer. Thanks \$\endgroup\$ – Incomputable Dec 16 '17 at 22:46
  • \$\begingroup\$ I was only considering comparisons. Given randomized input, the chance that the next value will be the new maximum is low, and goes down dramatically over time. The chance that the next value will be third or lower is high and goes up. You want to shortcut on the case that the next value is less than the current second greatest, to cut comparisons almost in half. On the other hand, you minimize swap/move operations, but that's trivial on int. I already did +1 though, nice answer. \$\endgroup\$ – Kenny Ostrom Dec 16 '17 at 22:48
  • \$\begingroup\$ @KennyOstrom, I actually got really interested in this. I’ll try to post benchmark tomorrow. I’m sure you’re right, I just want to test to what extent. I’ll post it as different answer, so you could +1 me again xD. On a more serious note, I think it conceptually differs from this post. \$\endgroup\$ – Incomputable Dec 16 '17 at 22:56

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.