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

// Recursive selection sort
//
// Previously, we implemented selection sort using
// a loop.
//
// The idea was:
//
//     1. Find the largest entry in the unsorted
//        portion of the array.
//
//     2. Swap that entry with the last entry in
//        the unsorted portion.
//
//     3. Repeat with an unsorted portion that is
//        one entry smaller.
//
// We can also describe exactly the same algorithm
// recursively.
//
// To sort an array containing n entries:
//
//     1. If n <= 1, the array is already sorted.
//
//     2. Otherwise, find the maximum entry among
//        all n entries.
//
//     3. Swap that maximum entry with the entry at
//        index n - 1.
//
//     4. Recursively sort the first n - 1 entries.
//
// Notice that after step 3, the last entry is in
// its correct final location.
//
// Therefore, the recursive call does not have to
// consider that entry again.
//
// This gives us a recurrence for the amount of
// work:
//
//     T(n) = T(n - 1) + Theta(n).
//
// We have already seen that a recurrence of this
// form gives:
//
//     T(n) = Theta(n^2).
//
// Thus, rewriting selection sort recursively does
// NOT make it more efficient.
//
// It simply gives us another way of expressing the
// same algorithm.

// Function declarations
int main();

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

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

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


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

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

    // Starting with an unsorted array, use
    // selection sort to sort it. Then change
    // entries to make the resulting array unsorted
    // again, and sort it again.

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

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

    selection_sort( data, N );

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


    // Make the array unsorted again.
    //
    // After sorting, the array is:
    //
    //     0.2, 1.9, 3.9, 4.0, 4.1,
    //     4.3, 6.8, 8.0, 8.4, 9.9
    //
    // Changing data[7] to -0.3 means the first
    // out-of-order entry is at index 7.

    data[7] = -0.3;

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

    selection_sort( data, N );

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


    // Make the array unsorted once more.
    //
    // After the preceding sort, changing data[3]
    // to 12.5 makes data[4] the first entry that
    // is less than its predecessor.

    data[3] = 12.5;

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

    selection_sort( data, N );

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


    // Test an array that is already sorted.

    double sorted[5]{
        -3.0, -1.0, 0.0, 4.0, 8.0
    };

    selection_sort( sorted, 5 );

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


    // Test an array in reverse order.

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

    selection_sort( reverse, 5 );

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


    // Repeated values are allowed in a sorted
    // array.

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

    selection_sort( repeated, 6 );

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


    // An array containing one entry is already
    // sorted.

    double single[1]{ 42.0 };

    selection_sort( single, 1 );

    assert( is_sorted( single, 1 ) == 1 );


    // An empty array is also considered sorted.
    //
    // Since capacity is zero, neither function
    // dereferences the pointer.

    selection_sort( nullptr, 0 );

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


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

    return 0;
}


// void selection_sort( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-11-01
// @version   2.0
//
// @param array
//     An array of double values that is to be
//     sorted.
//
// @param capacity
//     The number of entries in the array.
//
// @precondition
//     If capacity is greater than zero, array must
//     point to an array containing at least
//     capacity entries.
//
// @postcondition
//     The entries:
//
//         array[0], ..., array[capacity - 1]
//
//     are sorted into nondecreasing order.
//
// @algorithm
//
// If capacity <= 1, there is nothing to do.
//
// Otherwise:
//
//     1. Find the index of the maximum entry.
//
//     2. Swap the maximum entry with the final
//        entry.
//
//     3. Recursively sort the first capacity - 1
//        entries.
//
// After the swap, the maximum entry is in its
// correct final position:
//
//     [     remaining entries     ][ maximum ]
//
// We therefore leave that entry alone and solve
// the smaller problem:
//
//     [     remaining entries     ]
//
// This is exactly the structure required for a
// recursive algorithm:
//
//     solve one part of the problem,
//
//     reduce the problem to a smaller instance of
//     the SAME problem,
//
//     recursively solve that smaller problem.

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

    if ( capacity <= 1 ) {
        return;
    }

    std::size_t const max_index{
        find_max( array, capacity )
    };

    std::swap(
        array[max_index],
        array[capacity - 1]
    );

    selection_sort(
        array,
        capacity - 1
    );


    // This assertion is not required by the
    // algorithm.
    //
    // It is included here to verify the
    // postcondition while we are studying and
    // testing the recursive implementation.
    //
    // Notice that this assertion performs a linear
    // search through the array. Consequently, it
    // adds work to a debug build.
    //
    // If NDEBUG is defined, assertions disappear.

    assert(
        is_sorted( array, capacity )
        == capacity
    );
}


// std::size_t find_max( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
// @version   1.1
//
// @param array
//     An array of double values in which we are to
//     find the maximum entry.
//
// @param capacity
//     The number of entries in the array. This
//     must be positive.
//
// @returns
//     The first index at which the maximum entry
//     of the array is found.
//
// @precondition
//
//     capacity >= 1
//
// and array must point to an array containing at
// least capacity entries.
//
// @algorithm
//
// Assume initially that the maximum entry occurs
// at index zero.
//
// Step through the array from the second entry to
// the final entry.
//
// Whenever an entry is found that is greater than
// the current maximum, update max_index.
//
// Because we use:
//
//     >
//
// rather than:
//
//     >=
//
// if the maximum value occurs more than once, the
// FIRST occurrence is returned.
//
// It is nonsensical to ask for the maximum entry
// of an empty array, so capacity must be at least
// one.

std::size_t find_max(
    double      const array[],
    std::size_t const capacity
) {
    assert( capacity >= 1 );
    assert( array != nullptr );

    std::size_t max_index{ 0 };

    for ( std::size_t k{ 1 };
          k < capacity;
          ++k ) {
        if ( array[k] > array[max_index] ) {
            max_index = k;
        }
    }

    return max_index;
}


// std::size_t is_sorted( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
// @version   1.1
//
// @param array
//     An array of double values to be checked.
//
// @param capacity
//     The number of entries in the array.
//
// @returns
//     If the array is sorted:
//
//         capacity
//
//     is returned.
//
//     Otherwise, the first index k for which:
//
//         array[k] < array[k - 1]
//
//     is returned.
//
// @definition
//
// An array is sorted into nondecreasing order if:
//
//     array[i] <= array[j]
//
// whenever:
//
//     i <= j.
//
// Thus, repeated values are allowed.
//
// @algorithm
//
// Begin with the entry at index 1 and compare each
// entry with its predecessor.
//
// If:
//
//     array[k] < array[k - 1],
//
// then k is the first index at which the array is
// out of order.
//
// If no such index exists, return capacity.
//
// Empty arrays and arrays containing one entry are
// automatically sorted.

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;
}














































// Understanding the recursion
//
// Consider:
//
//     [ 4.0  1.0  7.0  3.0  2.0 ]
//
// We begin with capacity = 5.
//
// The maximum entry is:
//
//     7.0.
//
// We swap it with the last entry:
//
//     [ 4.0  1.0  2.0  3.0 | 7.0 ]
//
//                                      sorted
//
// The final entry is now in its correct location.
//
// We recursively sort only:
//
//     [ 4.0  1.0  2.0  3.0 ]
//
// The maximum of these four entries is:
//
//     4.0.
//
// Swap it with the last entry in this smaller
// problem:
//
//     [ 3.0  1.0  2.0 | 4.0  7.0 ]
//
//                                sorted
//
// Recursively sort:
//
//     [ 3.0  1.0  2.0 ]
//
// giving:
//
//     [ 2.0  1.0 | 3.0  4.0  7.0 ]
//
//                         sorted
//
// Finally:
//
//     [ 1.0 | 2.0  3.0  4.0  7.0 ]
//
//              sorted
//
// and when only one entry remains:
//
//     [ 1.0 ]
//
// there is nothing left to do.
//
//
//
// The recursive calls are therefore:
//
//     selection_sort(array, 5)
//
//         selection_sort(array, 4)
//
//             selection_sort(array, 3)
//
//                 selection_sort(array, 2)
//
//                     selection_sort(array, 1)
//
//                         return
//
//
// Notice that this is simple linear recursion.
//
// Each recursive call reduces the capacity by one.
//
//
//
// Why is capacity <= 1 the trivial case?
//
// An empty array:
//
//     [ ]
//
// is already sorted.
//
// An array containing one entry:
//
//     [ 42.0 ]
//
// is also already sorted.
//
// There are no two entries that can possibly be
// out of order.
//
// Therefore:
//
//     capacity <= 1
//
// is our trivial case.
//
//
//
// The recurrence
//
// Let T(n) describe the work required to sort an
// array containing n entries.
//
// To sort n entries:
//
//     1. find_max() examines n entries,
//
//     2. we perform a constant amount of work to
//        swap two entries, and
//
//     3. we recursively sort n - 1 entries.
//
// Therefore:
//
//     T(n) = T(n - 1) + Theta(n).
//
// If we focus specifically on the comparisons
// performed by find_max(), then:
//
//     find_max(array, n)
//
// performs:
//
//     n - 1
//
// comparisons.
//
// Thus, if C(n) counts those comparisons:
//
//     C(1) = 0
//
// and:
//
//     C(n) = C(n - 1) + n - 1.
//
// Expanding:
//
//     C(n)
//
//       = (n - 1)
//         + (n - 2)
//         + (n - 3)
//         + ...
//         + 2
//         + 1.
//
// Therefore:
//
//     C(n)
//
//       = n(n - 1)/2.
//
// Hence:
//
//     C(n) = Theta(n^2).
//
//
//
// This is the same number of comparisons as the
// iterative selection sort.
//
// That should not be surprising.
//
// We have changed HOW the repetition is expressed:
//
//     iteration:
//
//         for (...) {
//             ...
//         }
//
// versus:
//
//     recursion:
//
//         selection_sort(
//             array,
//             capacity - 1
//         );
//
// but we have not changed the underlying algorithm.
//
//
//
// Recursive does NOT mean faster
//
// This is an important point.
//
// Recursion is a programming technique.
//
// It does not, by itself, make an algorithm:
//
//     faster,
//     slower,
//     better,
//     or worse.
//
// The important question is:
//
//     What work does the algorithm perform?
//
// Our iterative selection sort performs:
//
//     (n - 1) + (n - 2) + ... + 1
//
// comparisons.
//
// Our recursive selection sort performs:
//
//     (n - 1) + (n - 2) + ... + 1
//
// comparisons.
//
// Both therefore require:
//
//     Theta(n^2)
//
// comparisons.
//
//
//
// Compare with our recurrence exercises
//
// We have now seen:
//
//     T(n) = T(n - 1) + 1
//
//         Theta(n)
//
//
//
//     T(n) = T(n - 1) + n
//
//         Theta(n^2)
//
//
//
//     T(n) = T(n/2) + 1
//
//         Theta(log(n))
//
//
//
//     T(n) = 2*T(n/2) + n
//
//         Theta(n*log(n))
//
//
// Recursive selection sort has the same basic form
// as:
//
//     T(n) = T(n - 1) + n.
//
// More precisely, if we count comparisons:
//
//     C(n) = C(n - 1) + n - 1.
//
// Thus:
//
//     C(n) = Theta(n^2).
//
//
//
// What happens on an already sorted array?
//
// Suppose:
//
//     [ 1  2  3  4  5 ]
//
// is already sorted.
//
// find_max() must still examine the entire
// unsorted portion.
//
// It performs:
//
//     4 comparisons,
//
// then:
//
//     3 comparisons,
//
// then:
//
//     2 comparisons,
//
// then:
//
//     1 comparison.
//
// Thus:
//
//     4 + 3 + 2 + 1 = 10
//
// comparisons.
//
//
//
// What happens on a reverse-sorted array?
//
// Suppose:
//
//     [ 5  4  3  2  1 ].
//
// find_max() still performs:
//
//     4 + 3 + 2 + 1 = 10
//
// comparisons.
//
// Thus, selection sort performs the same number of
// find_max() comparisons regardless of whether the
// original array is:
//
//     sorted,
//     reverse sorted,
//     random,
//     or nearly sorted.
//
// Consequently, both its best-case and worst-case
// comparison counts are:
//
//     Theta(n^2).
//
//
//
// What about the swap?
//
// We could write:
//
//     if ( max_index != capacity - 1 ) {
//         std::swap(
//             array[max_index],
//             array[capacity - 1]
//         );
//     }
//
// and thereby avoid swapping an entry with itself.
//
// That may reduce the number of actual swaps for
// some inputs.
//
// It does NOT change the number of comparisons
// required by find_max(), however.
//
// Therefore, it does not change the:
//
//     Theta(n^2)
//
// runtime.
//
// The unconditional swap used here makes the
// algorithm particularly simple.
//
//
//
// Why use find_max(array, capacity)?
//
// Another valid implementation is:
//
//     max_index = find_max(
//         array,
//         capacity - 1
//     );
//
// followed by a comparison between:
//
//     array[max_index]
//
// and:
//
//     array[capacity - 1].
//
// That works because it:
//
//     1. finds the maximum of the first n - 1
//        entries, and
//
//     2. separately compares that maximum with
//        the nth entry.
//
// However:
//
//     find_max(array, capacity)
//
// expresses the idea more directly:
//
//     Find the maximum of ALL entries in the
//     current problem.
//
// Then:
//
//     Put that maximum into its final position.
//
// Then:
//
//     Recursively solve the smaller problem.
//
// This version therefore mirrors the description of
// selection sort particularly closely.
//
//
//
// Recursion and the call stack
//
// There is one difference between the iterative
// and recursive implementations that does not
// appear in the comparison count.
//
// The recursive implementation creates calls:
//
//     selection_sort(array, n)
//
//     selection_sort(array, n - 1)
//
//     selection_sort(array, n - 2)
//
//     ...
//
//     selection_sort(array, 1).
//
// These calls occupy space on the call stack.
//
// The maximum recursion depth is proportional to:
//
//     n.
//
// Therefore, the recursive implementation requires:
//
//     Theta(n)
//
// additional stack space.
//
// The ordinary iterative selection sort requires
// only:
//
//     Theta(1)
//
// additional space.
//
// Thus, recursion gives us an elegant alternative
// description of selection sort, but it does not
// improve either its runtime or its memory usage.
//
//
//
// A subtle point about the assertion
//
// At the end of selection_sort(), we have:
//
//     assert(
//         is_sorted( array, capacity )
//         == capacity
//     );
//
// This is useful while testing.
//
// However, is_sorted() itself requires up to:
//
//     capacity - 1
//
// comparisons.
//
// Furthermore, this assertion executes at EVERY
// level of the recursion.
//
// Therefore, in a debug build, these assertions
// themselves contribute:
//
//     1 + 2 + 3 + ... + (n - 1)
//
// additional comparisons.
//
// That is:
//
//     Theta(n^2)
//
// additional work.
//
// The overall asymptotic runtime remains:
//
//     Theta(n^2),
//
// but the constant factor is larger.
//
// When the program is compiled with:
//
//     NDEBUG
//
// defined, assert() expressions are removed.
//
//
//
// Questions:
//
// 1. What is the trivial case for recursive
//    selection sort?
//
// 2. Why is an array containing one entry already
//    sorted?
//
// 3. Why is an empty array considered sorted?
//
// 4. After finding the maximum entry, where should
//    that entry be placed?
//
// 5. Once the maximum has been placed there, why
//    does the recursive call need to consider only
//    capacity - 1 entries?
//
// 6. Write the sequence of recursive calls made
//    when capacity is 5.
//
// 7. How many comparisons does:
//
//        find_max(array, n)
//
//    perform?
//
// 8. Write a recurrence for the number of
//    comparisons performed by recursive selection
//    sort.
//
// 9. Show that the exact number of find_max()
//    comparisons is:
//
//        n(n - 1)/2.
//
// 10. What is the asymptotic runtime of recursive
//     selection sort?
//
// 11. Does an already sorted array reduce the
//     number of comparisons?
//
// 12. Does a reverse-sorted array increase the
//     number of comparisons?
//
// 13. Does rewriting selection sort recursively
//     make it faster than the iterative version?
//
// 14. What additional memory cost is introduced by
//     the recursive implementation?
//
// 15. Why is:
//
//        find_max(array, capacity)
//
//     a more direct expression of selection sort
//     than searching only the first capacity - 1
//     entries and then separately examining the
//     final entry?
//
// 16. Why might the final assert() statements make
//     a debug build noticeably slower?
//
//
//
// The key recursive idea is:
//
//     Solve enough of the current problem to reduce
//     it to a smaller instance of the SAME problem.
//
// For selection sort:
//
//     Find the largest entry.
//
//     Put it where it belongs.
//
//     What remains?
//
//         The SAME sorting problem,
//
//     but now with:
//
//         one fewer entry.
//
// That observation leads directly to:
//
//     selection_sort(
//         array,
//         capacity - 1
//     );
//
// and is the essential step in recognizing a
// recursive algorithm.