#include <cstddef>
#include <iostream>

/***************************************************
 * Determining if an array is sorted
 *
 * An array is indexed from 0 through capacity - 1,
 * whatever its capacity.
 *
 * An array a is sorted if
 *
 *     a_0 <= a_1 <= a_2 <= a_3 <= ...
 *         <= a_(capacity - 2)
 *         <= a_(capacity - 1).
 *
 * The subscripts above use the notation of a
 * sequence, such as you might see in calculus.
 *
 * In C++, this condition would be written as
 *
 *     a[0] <= a[1]
 *     a[1] <= a[2]
 *     a[2] <= a[3]
 *     ...
 *     a[capacity - 2] <= a[capacity - 1].
 *
 * If any two neighbouring entries are not in
 * order, then the array is not sorted. For example,
 *
 *     1, 2, 5, 7, 12, 15, 19, 21, 25,
 *     32, 39, 45, 42, 57, 68, 71, 81
 *
 * is not sorted because 42 appears after 45, even
 * though 42 < 45.
 *
 * Write a function that determines whether an
 * array is sorted.
 ***************************************************/

// Function declarations
bool is_sorted_array(
    int const array[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    int array1[8]{
        15, 34, 40, 42, 59, 65, 69, 80
    };

    int array2[27]{
         2,  3, 17, 19, 22, 23, 29, 34, 38,
        38, 44, 46, 46, 46, 48, 50, 52, 57,
        65, 69, 73, 79, 88, 88, 93, 98, 99
    };

    std::cout << is_sorted_array( nullptr, 0 )
              << std::endl;
    std::cout << is_sorted_array( array1, 8 )
              << std::endl;
    std::cout << is_sorted_array( array2, 27 )
              << std::endl;

    array1[5]  = 12;
    array2[25] = 77;

    std::cout << is_sorted_array( array1, 8 )
              << std::endl;
    std::cout << is_sorted_array( array2, 27 )
              << std::endl;

    return 0;
}

/***************************************************
 * is_sorted_array
 *
 * Return true if the entries of the array are in
 * nondecreasing order, and return false otherwise.
 ***************************************************/
bool is_sorted_array(
    int const array[],
    std::size_t const capacity
) {
    return false;
}




































// Hint:
//
// If the capacity is N, then you must check the
// following pairs:
//
//          1.    array[0] <= array[1]
//          2.    array[1] <= array[2]
//          3.    array[2] <= array[3]
//          .                .
//          .                .
//          .                .
//      N - 1.    array[N - 2] <= array[N - 1]
//
// There are N - 1 pairs to check, rather than N.
//
// Notice that if k starts at 1, each comparison
// has the form
//
//     array[k - 1] <= array[k].
//
// Therefore, step through the array starting at
// index 1. As soon as two neighbouring entries are
// out of order, you know that the array is not
// sorted.
//
// What happens if the capacity is 0 or 1?
//
// In either case, the loop does not execute. There
// are no neighbouring entries that are out of
// order, so such an array is sorted.







































// One solution:

/*
bool is_sorted_array(
    int const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 1 }; k < capacity; ++k ) {
        if ( array[k - 1] > array[k] ) {
            return false;
        }
    }

    return true;
}
*/