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

// Selection sort
//
// We have already seen how to:
//
//     - determine whether an array is sorted;
//     - find the maximum entry in an array.
//
// We can combine these ideas to actually sort an
// array.
//
// Selection sort repeatedly finds the largest entry
// in the unsorted portion of the array and moves it
// to the end of that portion.
//
// For example:
//
//     4   1   7   3   5
//
// The maximum entry is 7, so move it to the end:
//
//     4   1   5   3 | 7
//
// Now ignore the 7. It is already in its final
// position.
//
// Find the maximum of the remaining entries:
//
//     4   1   5   3
//
// and move 5 to the end of that portion:
//
//     4   1   3 | 5   7
//
// Continue until the entire array is sorted.

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

    selection_sort( data, N );

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

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

    selection_sort( data, N );

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

    data[3] = 12.5;
    assert( is_sorted( data, N ) == 4 );

    selection_sort( data, N );

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

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

    double single[1]{ 42.0 };

    selection_sort( single, 1 );

    assert( single[0] == 42.0 );
    assert( is_sorted( single, 1 ) == 1 );

    // An empty array is also considered sorted.

    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-09-09
//
// @param array
//     An array of doubles that is to be sorted.
//
// @param capacity
//     The number of entries in the array.
//
// @algorithm
//     Starting with the last index of the array and
//     working backward:
//
//       - find the maximum entry from index 0
//         through index k;
//
//       - swap that maximum entry with the entry
//         at index k.
//
//     After this swap, the entry at index k is in
//     its final position.
//
//     Thus, after each pass, the sorted portion at
//     the right-hand end of the array grows by one
//     entry.

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

    for ( std::size_t k{ capacity }; k > 1; --k ) {
        // Find the maximum entry among
        //
        //     array[0], ..., array[k - 1].

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

        // Move that maximum entry to the end of the
        // unsorted portion.

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

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


// std::size_t find_max( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
//
// @param array
//     An array of doubles 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.
//
// @algorithm
//     Assume that the maximum entry occurs at
//     index 0.
//
//     Step through the array from the second entry
//     to the last entry.
//
//     Whenever an entry greater than the current
//     maximum is found, update max_index.
//
//     It is nonsensical to ask for the maximum
//     entry of an empty array, so capacity must be
//     at least 1.

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
//
// @param array
//     An array of doubles 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 at which an entry
//     is less than its predecessor is returned.
//
// @definition
//     An array is sorted if
//
//         array[i] <= array[j]
//
//     whenever
//
//         i <= j.
//
// @algorithm
//     Starting with index 1, compare each entry with
//     its predecessor.
//
//     As soon as an entry less than its predecessor
//     is found, return its index.
//
//     If every adjacent pair is in order, return
//     capacity.

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
















































// How does selection sort work?
//
// Consider:
//
//     index:   0   1   2   3   4
//
//     value:   4   1   7   3   5
//
// Initially, the entire array is unsorted:
//
//              unsorted
//              <---------------->
//
//              4   1   7   3   5
//
//
// Pass 1:
//
// Find the maximum entry:
//
//              4   1   7   3   5
//                      ^
//                     max
//
// Swap it with the final entry:
//
//              4   1   5   3 | 7
//                              ---
//                             sorted
//
// The 7 is now in its final position.
//
//
// Pass 2:
//
// Only search the unsorted portion:
//
//              4   1   5   3 | 7
//                      ^
//                     max
//
// Move 5 to the end of that portion:
//
//              4   1   3 | 5   7
//                          -------
//                           sorted
//
//
// Pass 3:
//
//              4   1   3 | 5   7
//              ^
//             max
//
// Move 4 to its final position:
//
//              3   1 | 4   5   7
//                      -----------
//                         sorted
//
//
// Pass 4:
//
//              3   1 | 4   5   7
//              ^
//
// Move 3 to its final position:
//
//              1 | 3   4   5   7
//                  ---------------
//                       sorted
//
//
// Only one entry remains.
//
// It must also be in its correct position:
//
//              1   3   4   5   7
//
// The array is sorted.
//
//
//
// An important idea: the sorted portion
//
// After every pass, one more entry has been placed
// in its final position.
//
// We can picture the algorithm as:
//
//     [       unsorted       | sorted ]
//
// then
//
//     [     unsorted     |   sorted   ]
//
// then
//
//     [   unsorted   |       sorted   ]
//
// then
//
//     [ unsorted |           sorted   ]
//
// until finally
//
//     [              sorted           ]
//
// The vertical line moves left by one position after
// every pass.
//
//
//
// How much work does find_max(...) require?
//
// Suppose find_max(...) is given n entries.
//
// It begins by assuming that array[0] contains the
// maximum.
//
// It then compares:
//
//     array[1]
//     array[2]
//     ...
//     array[n - 1]
//
// with the largest entry found so far.
//
// Therefore, it performs exactly
//
//     n - 1
//
// comparisons.
//
// Thus, find_max(...) has runtime
//
//     Theta(n).
//
//
//
// But selection_sort(...) calls find_max(...)
// repeatedly.
//
// This is where things become interesting.
//
// Suppose the original array contains 10 entries.
//
// The first call searches 10 entries:
//
//     9 comparisons
//
// The next call searches 9 entries:
//
//     8 comparisons
//
// Then:
//
//     7 comparisons
//
// and so on.
//
// The total number of comparisons is:
//
//     9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
//
// which equals:
//
//     45.
//
//
//
// What if there are n entries?
//
// The number of comparisons is:
//
//     (n - 1) + (n - 2) + ... + 3 + 2 + 1
//
// This is a familiar sum:
//
//     1 + 2 + 3 + ... + (n - 1)
//
// and its value is:
//
//     n(n - 1)
//     ----------
//         2
//
// Thus, selection sort performs exactly
//
//     n(n - 1)/2
//
// comparisons between array entries.
//
//
//
// What does that look like?
//
//     capacity       comparisons
//     --------------------------
//          10               45
//         100             4950
//        1000           499500
//       10000         49995000
//     1000000     499999500000
//
// For one million entries, selection sort performs
// almost
//
//     500000000000
//
// comparisons.
//
// That is approximately 500 billion comparisons.
//
//
//
// Where does n^2 come from?
//
// Expand the formula:
//
//     n(n - 1)/2
//
// to obtain:
//
//     (n^2 - n)/2.
//
// For large n, the n^2 term grows much faster than
// the n term.
//
// Thus, the amount of work grows approximately like
//
//     n^2/2.
//
// We therefore say that selection sort has runtime
//
//     Theta(n^2).
//
// It is also correct to say that it is
//
//     O(n^2).
//
// We describe this as quadratic runtime.
//
//
//
// What happens if the array doubles in size?
//
// Suppose n becomes 2n.
//
// The dominant term changes from approximately
//
//     n^2/2
//
// to
//
//     (2n)^2/2.
//
// But
//
//     (2n)^2 = 4n^2.
//
// Thus, doubling the size of the array causes
// selection sort to perform approximately four
// times as many comparisons.
//
//
//
//     capacity              comparisons
//     ---------------------------------
//          100                    4950
//          200                   19900
//
//         1000                  499500
//         2000                 1999000
//
//        10000                49995000
//        20000               199990000
//
//
// Doubling n approximately quadruples the work.
//
// This is characteristic of quadratic growth.
//
//
//
// Compare three algorithms we have now seen:
//
//                       worst-case runtime
//                       ------------------
//
//     binary search          O(log(n))
//
//     linear search          O(n)
//
//     selection sort         O(n^2)
//
//
// Be careful with this comparison.
//
// Binary search, linear search, and selection sort
// do NOT solve the same problem.
//
// Binary search and linear search find a value.
//
// Selection sort rearranges an entire array.
//
// Therefore, saying that binary search is "better"
// than selection sort would make no sense.
//
// The comparison is useful only for seeing how
// different growth rates behave as n increases.
//
//
//
//          approximate growth
//
// work
//  ^
//  |
//  |                              *
//  |                           *
//  |                        *       n^2
//  |                     *
//  |                  *
//  |              *
//  |          *
//  |      *                         n
//  |   *-----------------------
//  | *    _ _ _ _ _ _ _ _ _ _    log(n)
//  +--------------------------------------> n
//
//
// The exact shape of this sketch is not important.
//
// The important idea is:
//
//     log(n) grows very slowly;
//
//     n grows steadily;
//
//     n^2 grows increasingly quickly.
//
//
//
// Does selection sort become faster if the array
// is already sorted?
//
// Consider:
//
//     1   2   3   4   5
//
// It may seem that selection sort should notice that
// no work is required.
//
// But look at the algorithm.
//
// It still calls find_max(...) on all 5 entries.
//
// Then on the first 4.
//
// Then on the first 3.
//
// Then on the first 2.
//
// It therefore performs exactly the same number of
// comparisons:
//
//     4 + 3 + 2 + 1 = 10.
//
// Now consider:
//
//     5   4   3   2   1
//
// Again:
//
//     4 + 3 + 2 + 1 = 10.
//
// The arrangement of the values does not change the
// number of comparisons performed by this version of
// selection sort.
//
// Thus, measured by comparisons, its best-case and
// worst-case runtimes are both
//
//     Theta(n^2).
//
// This is quite different from linear search, binary
// search, and is_sorted(...), where an early result
// may allow the algorithm to stop.
//
//
//
// Comparisons and swaps are different
//
// Selection sort performs many comparisons, but it
// performs relatively few swaps.
//
// Each pass performs at most one swap.
//
// There are n - 1 passes.
//
// Thus, selection sort performs at most
//
//     n - 1
//
// swaps.
//
// In this implementation, std::swap(...) is called
// once on every pass, even when max_index == k - 1.
//
// We could instead write:
//
//     if ( max_index != k - 1 ) {
//         std::swap(
//             array[max_index],
//             array[k - 1]
//         );
//     }
//
// That avoids unnecessary self-swaps.
//
// It does NOT change the number of comparisons needed
// to find the maximum entries.
//
// Consequently, it does not change the quadratic
// asymptotic runtime.
//
//
//
// Questions:
//
// 1. Why is the largest entry placed at the end of
//    the unsorted portion after every pass?
//
// 2. Once an entry has been placed in the sorted
//    portion, why do we never need to examine it
//    again?
//
// 3. How many comparisons does find_max(...) perform
//    when given 100 entries?
//
// 4. How many entries are searched on the second
//    pass of selection sort if the original array
//    contains 100 entries?
//
// 5. Why is the total number of comparisons
//
//        (n - 1) + (n - 2) + ... + 2 + 1
//
//    rather than simply n?
//
// 6. If selection sort takes approximately four
//    times as much work when n doubles, what does
//    that suggest about its growth rate?
//
// 7. If the array is already sorted, does this
//    implementation perform fewer comparisons?
//
// 8. Could we change the algorithm so that it avoids
//    calling std::swap(...) when the maximum is
//    already in the correct position?
//
// 9. Would avoiding those unnecessary swaps change
//    the Theta(n^2) runtime?
//
//
//
// One final question:
//
// Selection sort finds ONE entry that belongs in its
// final position during each pass.
//
//     pass 1:       one entry placed
//     pass 2:       one entry placed
//     pass 3:       one entry placed
//        ...
//
// This requires approximately n passes, and finding
// the appropriate entry on each pass requires work
// proportional to the size of the remaining array.
//
// This gives us quadratic runtime.
//
// Is it possible to sort an array without repeatedly
// searching almost the entire remaining array for
// just one entry?
//
// In other words:
//
//     Can we somehow make better use of the work
//     performed during each pass?
//
// The answer is yes.
//
// Later sorting algorithms will show that sorting
// does not inherently require Theta(n^2) work.