CODEWITHSUNDEEP
c++algorithmrecursionvectordivide-and-conquer
Lastrevio2
Lastrevio2

Reputation: 51

Check if a vector is ordered using divide et impera algorithm

I am trying to check if a vector is ordered using the divide and conquer algorithm, here's the code I wrote so far: 

#include <iostream>
#include <vector>

using namespace std;

bool isOrdered(std::vector <int> v, int left, int right)
{
int mid = (left + right)/2;

if (left == right){
    if (left == 0)
        return true;
    else
        return v[left-1] <= v[left];
}
else if (left + 1 == right)
{
    if (v[left] <= v[right])
        return true;
    else
        return false;
}
else if (left > right)
{
    if (v[left] > v[right])
        return true;
    else
        return false;
}
else
{
    return isOrdered(v, left, mid) && isOrdered(v, mid+1, right);
}
}

int main()
{
std::vector <int> v = {2, 2, 3, 2, 2};
cout << isOrdered(v, 0, v.size() - 1);
return 0;
}

It can't seem to work for certain cases and while debugging I kept adding specific base cases to make it work for one input but that would not make it work for another input, and I kept doing that until I realized I had an algorithmic error. I basically thought of it like this: Divide the vector up into sub-vectors and if all sub-vectors are ordered then the whole vector is ordered. However this approach very quickly breaks down. If the input length is not a power of 2 then it will eventually break it down into certain sub-vectors of length 1 which will always be ordered. For example what if the input is 2 2 3 2 2? The sub-vectors are {2, 2}, {3} and {2, 2} and all of them are ordered but the whole vector is not.

So how should I think this problem instead? I tried to make it work for sub-vectors of length 1 by adding that return v[left-1] <= v[left]; line but it still breaks down.

Upvotes: 2

Views: 769

Answers (3)

Jarod42
Jarod42

Reputation: 217293

Beginning with recursion:

range is ordered if both subranges is ordered and if last item of "low" range is lower than first item of "high" range:

return isOrdered(v, left, mid - 1) && isOrdered(v, mid, right) && v[mid - 1] <= v[mid];

Remains the stop condition: when range is empty (cannot happen from argument) or has only one element. Those are ordered ranges.

So we got:

bool isOrdered(const std::vector<int>& v, std::size_t left, std::size_t right)
{
    if (left == right) { // Only one element
        return true;
    } else {
        const auto mid = (left + right + 1) / 2;
        return v[mid - 1] <= v[mid]
            && isOrdered(v, left, mid - 1)
            && isOrdered(v, mid, right);
    }
}

Upvotes: 2

alan23273850
alan23273850

Reputation: 262

#include <iostream>
#include <vector>

using namespace std;

bool isOrdered(const vector <int> &v, int left, int right) {
    int mid = (left + right)/2;
    if (left == right)
        return true;
    else
        return v[mid]<=v[mid+1] && isOrdered(v, left, mid) && isOrdered(v, mid+1, right);
}

int main()
{
    vector <int> v = {2, 2, 3, 2, 2};
    cout << isOrdered(v, 0, v.size() - 1);
    return 0;
}

Upvotes: 0

Dominique
Dominique

Reputation: 17493

Why do you even use this "difficult" algorithm? In order to check if a vector is ordened, every member (v[i]) can't be larger than the next (v[i+1]).

The "divide-and-conquer" algorithm is more useful, for instance, to find something in an already ordered vector, but for checking whether or not a vector is ordered, a simple linear algorithm is much better (because of readability).

Upvotes: 1

Related Questions