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

// Checking whether an array is sorted
//
// An array is sorted in nondecreasing order
// if every entry is greater than or equal
// to the preceding entry.
//
// For example:
//
//     {1.0, 2.0, 2.0, 5.0}
//
// is sorted. Repeated values are permitted.
//
// However,
//
//     {1.0, 3.0, 2.0, 5.0}
//
// is not sorted, because the entry at
// index 2 is less than the preceding entry.
//
// Implement a function that returns:
//
// - capacity, if the array is sorted;
//
// - otherwise, the first index at which
//   an entry is less than its predecessor.
//
// Arrays with zero or one element are
// considered sorted.
//
// If capacity is zero, array may be nullptr.

// Function declarations
std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity
);

int main();

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

    double data[N]{
        0.2, 1.9, 3.9, 4.0, 4.1,
        4.3, 6.9, 8.0, 8.4, 9.9
    };

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

    // Initially, the entire array is sorted.

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

    // Change individual entries so that
    // progressively earlier entries become
    // smaller than their predecessors.

    data[7] = -0.3;
    assert( is_sorted( data, N ) == 7 );

    data[5] = 0.0;
    assert( is_sorted( data, N ) == 5 );

    data[1] = 0.1;
    assert( is_sorted( data, N ) == 1 );

    // An empty array is sorted.

    assert( is_sorted( nullptr, 0 ) == 0 );

    // An array with one element is sorted.

    double single[1]{ 42.0 };
    assert( is_sorted( single, 1 ) == 1 );

    // Repeated values are permitted.

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

    assert( is_sorted( repeated, 5 ) == 5 );

    // A decreasing pair at the very end
    // must also be detected.

    double last_pair[5]{
        1.0, 2.0, 3.0, 5.0, 4.0
    };

    assert( is_sorted( last_pair, 5 ) == 4 );

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

    return 0;
}

// std::size_t is_sorted( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
//
// @param array
//     An array of doubles to be checked.
//
// @param capacity
//     The number of entries in the array.
//
// @returns
//     capacity if the array is sorted;
//     otherwise, the first index k for
//     which array[k] < array[k - 1].
//
// @definition
//     An array is sorted in nondecreasing
//     order if array[i] <= array[j]
//     whenever i <= j.
//
// @algorithm
//     Starting at index 1, compare each
//     entry with its predecessor.
//
//     As soon as an entry is less than
//     its predecessor, return its index.
//
//     If every adjacent pair is in order,
//     return capacity.
//
// @precondition
//     If capacity is greater than zero,
//     array must point to at least
//     capacity valid doubles.

std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity
) {
    assert( (capacity == 0) || (array != nullptr) );

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

    return capacity;
}




































// Questions:
//
// 1. Why does the loop begin at index 1
//    rather than index 0?
//
// 2. Why does the function return capacity
//    when the array is sorted?
//
// 3. Why are arrays with zero or one
//    element considered sorted?
//
// 4. Why does the function use < rather
//    than <= when comparing adjacent
//    elements?
//
// 5. What would happen if the original
//    implementation were called with
//    capacity equal to zero?
//
// 6. If the function returns 7, what
//    can you conclude about the entries
//    at indices 6 and 7?
//
// 7. If the function returns capacity,
//    must it have compared every pair
//    of adjacent elements?




































// Answers:
//
// 1. Index 0 has no predecessor.
//    The first pair to compare is
//    array[0] and array[1].
//
// 2. Valid indices range from 0 through
//    capacity - 1. Returning capacity
//    indicates that no out-of-order
//    entry was found.
//
// 3. Neither array contains an adjacent
//    pair that could be out of order.
//
// 4. Repeated values are permitted.
//    The array is unsorted only when
//    an entry is strictly less than
//    its predecessor.
//
// 5. Since capacity is unsigned,
//    capacity - 1 would wrap around
//    to a very large value.
//
//    The loop would then attempt to
//    access elements of an empty array,
//    causing undefined behavior.
//
// 6. array[7] < array[6].
//
//    Moreover, all preceding adjacent
//    pairs were found to be in order.
//
// 7. Yes, provided capacity is at least
//    two. The function must compare
//    every adjacent pair before it can
//    conclude that the array is sorted.







// Runtime analysis:
// How much work does checking an array require?
//
// We previously examined linear search and counted
// how many entries must be examined before a value
// is found.
//
// We can apply the same reasoning to checking whether
// an array is sorted.
//
// For this algorithm, the operation we will count is
// the comparison
//
//     array[k] < array[k - 1]
//
// That is, we count how many pairs of adjacent entries
// must be compared.
//
//
// Questions:
//
// 1. If the array has capacity n, how many pairs of
//    adjacent entries does it contain?
//
// 2. What is the minimum number of comparisons the
//    function can perform for an array containing at
//    least two entries?
//
// 3. What is the maximum number of comparisons the
//    function can perform?
//
// 4. If the capacity of the array doubles,
//    approximately how does the maximum number of
//    comparisons change?
//
// 5. What are the best-case and worst-case asymptotic
//    runtimes of is_sorted(...)?
//
// 6. How do these compare with the best-case and
//    worst-case runtimes of linear search?
//
//
// Comparison counts:
//
//     Array        First pair        Entire array
//     capacity     out of order      sorted
//     ---------------------------------------------
//          10           1                  9
//         100           1                 99
//        1000           1                999
//     1000000           1             999999
//
//
// Introducing asymptotic runtime
//
// An array containing n entries has
//
//     n - 1
//
// adjacent pairs, provided n is at least 1.
//
// In the worst case, the algorithm must compare every
// adjacent pair.
//
// Thus, as n grows, the maximum number of comparisons
// grows proportionally to n.
//
//
// Best case:
//
// Suppose the first pair is out of order.
//
// For example:
//
//     {2.0, 1.0, 3.0, 4.0, 5.0}
//
// The function discovers after only one comparison
// that the array is not sorted.
//
// The amount of work does not depend on the capacity
// of the array.
//
// Thus, for arrays containing at least two entries,
// the best-case runtime is
//
//     O(1).
//
//
// Worst case:
//
// Suppose the entire array is sorted.
//
// For example:
//
//     {1.0, 2.0, 3.0, 4.0, 5.0}
//
// The function cannot know that the array is sorted
// until it has examined every adjacent pair.
//
// An array containing n entries has n - 1 adjacent
// pairs, so the function performs
//
//     n - 1
//
// comparisons.
//
// The same amount of work is required if the only
// out-of-order pair is the final pair.
//
// Thus, the worst-case runtime is
//
//     O(n).
//
// More precisely, the worst-case number of comparisons
// grows linearly with n, so it is also
//
//     Theta(n).
//
//
// Why are adjacent comparisons sufficient?
//
// Checking whether an array is sorted does not require
// comparing every entry with every other entry.
//
// Suppose we establish that
//
//     array[0] <= array[1]
//     array[1] <= array[2]
//     array[2] <= array[3]
//     ...
//
// From these comparisons, it follows that
//
//     array[0] <= array[1] <= array[2] <= array[3] <= ...
//
// Thus, comparing each entry with its immediate
// predecessor is sufficient to establish that the
// entire array is sorted.
//
//
// Comparison with linear search
//
// Linear search and is_sorted(...) have similar
// asymptotic runtimes.
//
// In the best case, each may return after performing
// only one comparison:
//
//     linear search: the desired value is first;
//
//     is_sorted:     the first pair is out of order.
//
// Thus, both have best-case runtime
//
//     O(1).
//
// In the worst case, both must examine an amount of
// information proportional to the capacity of the
// array:
//
//     linear search: n comparisons;
//
//     is_sorted:     n - 1 comparisons.
//
// Thus, both have worst-case runtime
//
//     O(n).
//
// The fact that one performs n comparisons while the
// other performs n - 1 comparisons does not change
// their asymptotic runtimes.
//
// Both grow linearly as n grows.
//
//
// A question leading into sorting algorithms:
//
// Suppose that instead of merely checking whether an
// array is sorted, you actually wanted to sort it.
//
// Could you always accomplish this by making just one
// pass through the array?
//
// Or might you have to revisit some entries several
// times?
//
// If you had to make approximately n passes through
// an array containing n entries, and each pass
// examined approximately n entries, approximately
// how much work would be required?
//
// This question will become important when we begin
// comparing the runtimes of different sorting
// algorithms.