#include <cassert>
#include <cstddef>
#include <iostream>

// Seven variations on checking whether an array is sorted
//
// Each function claims to determine whether an array
// is sorted in nondecreasing order.
//
// The required return value is:
//
//   - capacity, if the array is sorted;
//
//   - otherwise, the first index k for which
//     array[k] < array[k - 1].
//
// An array with zero or one element is sorted.
// Repeated values are permitted.
//
// Not all seven functions are correct.
//
// For each function:
//
// 1. Determine whether it is correct for every
//    permitted input.
//
// 2. If it is incorrect, provide a counterexample.
//    Use the smallest array you can.
//
// 3. Explain the error and correct the function.
//
// 4. Determine its worst-case runtime, assuming
//    any errors have been corrected.
//
// Do not run all seven functions indiscriminately.
// Some contain undefined behavior, and one can
// enter an infinite loop.

// Function declarations

std::size_t is_sorted_1(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_2(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_3(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_4(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_5(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_6(
    double      const array[],
    std::size_t const capacity
);

std::size_t is_sorted_7(
    double      const array[],
    std::size_t const capacity
);

int main();

// Function definitions

int main() {
    std::size_t const N{ 10 };

    double data[N]{
        0.1, 1.2, 2.3, 3.4, 4.5,
        5.6, 6.7, 7.8, 8.9, 9.0
    };

    std::cout << "Starting testing"
              << std::endl;

    // Version 2 can be tested with these
    // ordinary finite values.

    assert( is_sorted_2( data, N ) == N );

    data[7] = 0.0;

    assert( is_sorted_2( data, N ) == 7 );

    double repeated[4]{
        1.0, 2.0, 2.0, 3.0
    };

    assert( is_sorted_2( repeated, 4 ) == 4 );
    assert( is_sorted_2( nullptr, 0 ) == 0 );

    // Examine the remaining functions before
    // attempting to run them. Some test cases
    // can cause invalid memory accesses or
    // infinite loops.

    std::cout << "Finished testing"
              << std::endl;

    return 0;
}

// Version 1

std::size_t is_sorted_1(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 };
          k < capacity - 1;
          ++k ) {
        if ( array[k] > array[k + 1] ) {
            return k + 1;
        }
    }

    return capacity;
}

// Version 2

std::size_t is_sorted_2(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 1 };
          k < capacity;
          ++k ) {
        if ( array[k - 1] - array[k] > 0 ) {
            return k;
        }
    }

    return capacity;
}

// Version 3
//
// The spelling of std::size_t has been
// corrected so that this function compiles.
// Its algorithm has not been corrected.

std::size_t is_sorted_3(
    double      const array[],
    std::size_t const capacity
) {
    std::size_t k{ 1 };

    while ( k < capacity ) {
        if ( array[k - 1] > array[k] ) {
            break;
        }
    }

    return k;
}

// Version 4

std::size_t is_sorted_4(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 };
          k < capacity;
          ++k ) {
        if ( array[k] > array[k + 1] ) {
            return k + 1;
        }
    }

    return capacity;
}

// Version 5

std::size_t is_sorted_5(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 1 };
          k < capacity;
          ++k ) {
        if ( array[k] <= array[k - 1] ) {
            return k + 1;
        }
    }

    return capacity;
}

// Version 6

std::size_t is_sorted_6(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 };
          k < capacity - 1;
          ++k ) {
        if ( array[k] >= array[k + 1] ) {
            return k + 1;
        }
    }

    return capacity;
}

// Version 7

std::size_t is_sorted_7(
    double      const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 };
          k < capacity - 1;
          ++k ) {
        if ( array[k] > array[k + 1] ) {
            return k;
        }
    }

    return capacity;
}



// Find a counterexample
//
// Try to identify a counterexample for each function
// before reading the explanation below.
//
//
// Version 1
//
// This function fails when the capacity is zero.
//
// If
//
//     capacity == 0
//
// then the expression
//
//     capacity - 1
//
// does not evaluate to -1. The type std::size_t is an
// unsigned integer type, so the subtraction underflows
// and produces a very large value.
//
// Consequently, the loop may attempt to access entries
// in an array that has no entries.
//
// A better approach is to start at index 1 and compare
// each entry with its predecessor:
//
//     for ( std::size_t k{ 1 }; k < capacity; ++k ) {
//         if ( array[k] < array[k - 1] ) {
//             return k;
//         }
//     }
//
//
// Version 2
//
// This function works correctly for ordinary finite
// floating-point values:
//
//     if ( array[k - 1] - array[k] > 0 )
//
// is equivalent to asking whether
//
//     array[k - 1] > array[k].
//
// However, the subtraction is unnecessary. It is clearer
// to directly compare the two values:
//
//     if ( array[k] < array[k - 1] ) {
//         return k;
//     }
//
// Direct comparison also avoids unnecessary floating-point
// arithmetic and behaves more naturally when infinities
// are present.
//
// Arrays containing NaN require us to separately define
// what we mean by "sorted", since ordinary comparisons
// involving NaN are false.
//
//
// Version 3
//
// Consider the sorted array
//
//     {1.0, 2.0}
//
// Initially,
//
//     k == 1.
//
// The condition
//
//     k < capacity
//
// is true, and
//
//     array[0] > array[1]
//
// is false.
//
// Nothing in the body of the loop changes k, however.
// Consequently, the same comparison is performed again
// and again, and the loop never terminates.
//
// We must increment k:
//
//     while ( k < capacity ) {
//         if ( array[k - 1] > array[k] ) {
//             break;
//         }
//
//         ++k;
//     }
//
// There is another problem. If capacity is zero, k is
// initialized to 1, the loop is skipped, and the function
// incorrectly returns 1 rather than capacity, which is 0.
//
//
// Version 4
//
// Consider an array containing just one entry:
//
//     {1.0}
//
// The loop begins with
//
//     k == 0
//
// and the condition
//
//     k < capacity
//
// is true.
//
// The function then compares
//
//     array[0] > array[1]
//
// but array[1] does not exist.
//
// More generally, if the array is sorted, the final
// iteration compares
//
//     array[capacity - 1]
//
// with
//
//     array[capacity],
//
// and array[capacity] is outside the array.
//
// Accessing this entry causes undefined behavior.
//
//
// Version 5
//
// There are two errors.
//
// First, consider
//
//     {1.0, 1.0, 2.0}
//
// This array is sorted because repeated values are
// permitted. However, the comparison
//
//     array[k] <= array[k - 1]
//
// is true for the first two entries.
//
// The comparison should instead be
//
//     array[k] < array[k - 1].
//
// Second, if an out-of-order entry is found at index k,
// the function returns
//
//     k + 1
//
// rather than
//
//     k.
//
// Thus, the corrected statement is:
//
//     if ( array[k] < array[k - 1] ) {
//         return k;
//     }
//
//
// Version 6
//
// Consider
//
//     {1.0, 1.0}
//
// This array is sorted because repeated values are
// permitted.
//
// However,
//
//     array[0] >= array[1]
//
// is true, so the function incorrectly reports that
// the entry at index 1 is out of order.
//
// The comparison should use > rather than >=.
//
// This function also has the same capacity-zero problem
// as Version 1 because it evaluates
//
//     capacity - 1
//
// when capacity has type std::size_t.
//
//
// Version 7
//
// Consider
//
//     {2.0, 1.0}
//
// The first entry that is out of order is the entry
// at index 1.
//
// The function correctly detects that
//
//     array[0] > array[1],
//
// but it returns
//
//     k
//
// which is 0.
//
// It should return
//
//     k + 1.
//
// This function also has the same capacity-zero problem
// as Versions 1 and 6.
//
//
// Summary
//
// Version 1:
//     Incorrect when capacity is zero.
//
// Version 2:
//     Correct for ordinary finite values, although the
//     subtraction is unnecessary and direct comparison
//     is preferable.
//
// Version 3:
//     Fails to increment k and may therefore enter an
//     infinite loop. It also returns the wrong value
//     when capacity is zero.
//
// Version 4:
//     May access array[capacity], which is outside
//     the array.
//
// Version 5:
//     Incorrectly rejects equal adjacent entries and
//     returns the wrong index.
//
// Version 6:
//     Incorrectly rejects equal adjacent entries and
//     also fails when capacity is zero.
//
// Version 7:
//     Returns the index of the preceding entry rather
//     than the first out-of-order entry, and also fails
//     when capacity is zero.
//
//
// All seven functions can be corrected using the same
// straightforward algorithm:
//
// std::size_t is_sorted(
//     double      const array[],
//     std::size_t const capacity
// ) {
//     for ( std::size_t k{ 1 };
//           k < capacity;
//           ++k ) {
//         if ( array[k] < array[k - 1] ) {
//             return k;
//         }
//     }
//
//     return capacity;
// }
//
//
//
// Runtime analysis
//
// These seven functions are written somewhat differently.
// Some use a for loop, one uses a while loop, some compare
// adjacent entries directly, and another subtracts them.
//
// Suppose all the errors have been corrected.
//
// Does any version have a fundamentally different runtime?
//
//
// Questions:
//
// 1. If an array has n entries, how many adjacent pairs
//    does it contain?
//
// 2. How many comparisons are required to establish that
//    the entire array is sorted?
//
// 3. If the first pair is out of order, how many
//    comparisons are required?
//
// 4. If the capacity of a sorted array is doubled,
//    approximately what happens to the number of
//    comparisons?
//
// 5. Does replacing a for loop with a while loop change
//    the asymptotic runtime?
//
// 6. What are the best-case and worst-case asymptotic
//    runtimes of these algorithms once they are corrected?
//
//
//
// Answers:
//
// 1. An array containing n entries has n - 1 adjacent
//    pairs, provided n is greater than zero.
//
// 2. If the array is sorted, every adjacent pair must
//    be examined. Thus, the function performs n - 1
//    comparisons.
//
// 3. If the first pair is out of order, only one
//    comparison is required.
//
// 4. Doubling the capacity approximately doubles the
//    maximum number of comparisons.
//
// 5. No. Replacing a for loop with a while loop may
//    slightly change the individual operations that
//    are performed, but it does not change how the
//    amount of work grows as n increases.
//
// 6. For an array containing at least two entries,
//    the best case requires only one comparison.
//    Consequently, the best-case runtime is
//
//        O(1).
//
//    In the worst case, all n - 1 adjacent pairs must
//    be compared. Consequently, the worst-case runtime
//    is
//
//        O(n).
//
//
// An important observation:
//
// Different-looking code does not necessarily have a
// different asymptotic runtime.
//
// For example, suppose one correct implementation
// performs approximately
//
//     n
//
// operations while another performs approximately
//
//     3n + 5
//
// operations.
//
// The second may perform more individual operations,
// but in both cases the amount of work grows in direct
// proportion to n.
//
// We therefore describe both algorithms as having
// linear runtime, or
//
//     O(n).
//
//
// There is also an important distinction between
// correctness and efficiency.
//
// An algorithm that quickly returns the wrong answer
// is not better than a slower algorithm that returns
// the correct answer.
//
// Thus, before analyzing the runtime of an algorithm,
// we must first establish that the algorithm is correct.