CODEWITHSUNDEEP
c++
user3059197
user3059197

Reputation: 13

Determine whether the following function determines if array is sorted in ascending order

I am trying to trace this recursive call, but my assumption that it determines whether an array is sorted in ascending order is incorrect. Any suggestions on how I can do this?

bool g(int a[], int l, int r) {

     if(l==r)
        return true;
     if((r-l)==1)
        return (a[l] > a[r]);

     else {
        int m = (l+r)/2;
        return (a,l,m) && (a[m] > a[m+1]) && g(a,m+1,r);
    }
}

Upvotes: 1

Views: 136

Answers (2)

kvark
kvark

Reputation: 5351

The last return line should be:

return g(a,l,m) && (a[m] > a[m+1]) && g(a,m+1,r);

If you just write (a,l,m) C++ treats it as a comma operator, the result of which is just the last argument (m in your case, which is mostly "true" and prevents anything else being evaluated).

Upvotes: 2

Tony Delroy
Tony Delroy

Reputation: 106116

Walking you through how to analyse this:

  • g() works on an array of ints
  • l and r are used to index into the array
  • l == r is a termination condition... always returning true
  • r - l == 1 implies r is expected to be more than l, cementing an understanding of them as the left (lower index) and right ends of a range within the array: if l and r are side-by-side, then a[l] > a[r] checks for descending order
  • m = (l + r) / 2 - this is finding a midway point between the left and right ends, but crucially if l + r is odd it rounds down, so we'd better consider this "edge case" when understanding the algorithm
  • the return statement...
    • as kvark says in his answer, it's certainly meant to be g(a,l,m)... which would mean do the same kind of processing on the range l..m
    • && a(m) > a[m+1] && tests for descending order
    • g(a, m+1, r) does the same kind of processing on the range m+1..r

So... when r-l > 1 there are 2 or more elements to be considered. If we start at the smallest gap not special-cased (2) and work our way through larger gaps until we've established a clear trend of relying on proven-working smaller gaps:

  • if r-l == 2: m = 1, resolves to g(a,l,l+1) (which tests a[l] > a[l+1]) && a[l+1] > a[l+2] && g(a,l+2,l+2) (latter always true), so two important tests are a[l] > a[l+1] > a[l+2] (using maths semantics)
  • if r-l == 3: m = 1, as above except the last recursive call becomes g(a,l+2,l+3), which will test a[l+2] > a[l+3], so it's working to ensure they're all in order
  • if r-l == 4, m = 2, resolves to g(a, l, l+2) (which we proved to ourselves works above) && a[l+2] > a[l+3] && g(a,l+3,l+4) (for the last, r-l == 1 which we also observed above works)...

Clearly when r-l == 5 g() recurses to test r-l gaps of 2 and 3 (proven above), 6 tests 3 and 3, 7 4 and 3 etc... so we can see if works for any size r-l gap.

Upvotes: 0

Related Questions