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

// Alternative selection sort
//
// Previously, our selection sort worked from right
// to left:
//
//     - find the largest entry in the unsorted
//       portion of the array;
//
//     - move that entry to the right-hand end of
//       the unsorted portion.
//
// For example:
//
//     4   1   7   3   5
//
// becomes
//
//     4   1   5   3 | 7
//
// and then
//
//     4   1   3 | 5   7
//
//
// Author a selection sort that works in the opposite
// direction.
//
// Starting with index 0 and working toward the end
// of the array:
//
//     - find the smallest entry from the current
//       index to the end of the array;
//
//     - swap that smallest entry with the entry at
//       the current index.
//
// Thus, the sorted portion of the array should grow
// from left to right:
//
//     [       unsorted       ]
//
//     [ sorted |   unsorted  ]
//
//     [   sorted   | unsorted]
//
//     [        sorted         ]
//
//
// You may update the given functions or define new
// functions as you see fit.
//
// Test your implementation using the tests below.

// Function declarations
int main();

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

std::size_t find_min(
    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
    };

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

    // Sort an unsorted array.

    selection_sort( data, N );

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

    // Make the array unsorted by introducing a
    // value that is too small.

    data[7] = -0.3;

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

    selection_sort( data, N );

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

    // Make the array unsorted by introducing a
    // value that is too large.

    data[3] = 12.5;

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

    selection_sort( data, N );

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

    // Test an array containing repeated values.

    double repeated[6]{
        3.0, 1.0, 3.0, 2.0, 1.0, 2.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( 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( ... )
//
// @param array
//     An array of doubles that is to be sorted.
//
// @param capacity
//     The number of entries in the array.
//
// @algorithm
//     Starting with index 0 and moving toward the
//     end of the array:
//
//       - find the smallest entry from the current
//         index to the end of the array;
//
//       - swap that entry with the entry at the
//         current index.
//
//     After each pass, one more entry at the
//     left-hand end of the array is in its final
//     position.

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

    // Your implementation here.

}


// std::size_t find_min( ... )
//
// @param array
//     An array of doubles in which we are to find
//     the minimum entry.
//
// @param capacity
//     The number of entries in the array.
//     This must be positive.
//
// @returns
//     The first index at which the minimum entry
//     of the array is found.
//
// @algorithm
//     Assume the minimum entry occurs at index 0.
//
//     Step through the remaining entries and update
//     the index whenever a smaller entry is found.

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

    // Your implementation here.

    return 0;
}


// std::size_t is_sorted( ... )
//
// @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.

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









































// Hints
//
// The previous selection sort repeatedly found the
// maximum entry:
//
//     [       unsorted       | sorted ]
//                              ^
//                              |
//                         place maximum
//
// This version should repeatedly find the minimum:
//
//     [ sorted |       unsorted       ]
//              ^
//              |
//         place minimum
//
//
// Be careful:
//
// find_min(...) as declared above searches an array
// beginning at array[0].
//
// On the first pass, this is exactly what you want:
//
//     find_min( array, capacity )
//
// On later passes, however, the sorted entries at
// the beginning should no longer be searched.
//
// Remember that if k is an index, then
//
//     array + k
//
// points to the entry at index k.
//
// Thus, you can treat part of an array as though it
// were itself an array:
//
//     original array:
//
//         4   1   7   3   5
//         ^
//         array
//
//     beginning at index 2:
//
//         4   1   7   3   5
//                 ^
//                 array + 2
//
// If find_min(...) is passed array + k, remember
// that the index it returns is relative to that
// smaller portion of the array.
//
//
//
// No solution is provided for this exercise.
//
// You have already seen all of the pieces required
// to implement it. If you get stuck, compare your
// approach with the previous selection sort, talk
// through the algorithm with another student, and
// trace a small example by hand.
//
//
//
// How should this version behave?
//
// Consider:
//
//     index:   0   1   2   3   4
//
//     value:   4   1   7   3   5
//
//
// Pass 1:
//
// Find the minimum of the entire array:
//
//              4   1   7   3   5
//                  ^
//                 min
//
// Move it to index 0:
//
//              1 | 4   7   3   5
//              -
//            sorted
//
//
// Pass 2:
//
// Do not search the 1 again.
//
// Search only:
//
//                  4   7   3   5
//                          ^
//                         min
//
// Move 3 to index 1:
//
//              1   3 | 7   4   5
//              -----
//              sorted
//
//
// Pass 3:
//
// Search:
//
//                      7   4   5
//                          ^
//                         min
//
// Move 4 into position:
//
//              1   3   4 | 7   5
//              ---------
//                sorted
//
//
// Pass 4:
//
// Search:
//
//                          7   5
//                              ^
//                             min
//
// Move 5 into position:
//
//              1   3   4   5 | 7
//              -------------
//                   sorted
//
//
// Only one entry remains, so the entire array is
// sorted.
//
//
//
// Compare the two versions
//
// The original selection sort grew a sorted portion
// from the RIGHT:
//
//     [       unsorted       | sorted ]
//
//     [     unsorted     |   sorted   ]
//
//     [   unsorted   |       sorted   ]
//
//     [ unsorted |           sorted   ]
//
//     [              sorted           ]
//
//
// This version grows a sorted portion from the LEFT:
//
//     [       unsorted       ]
//
//     [ sorted |       unsorted       ]
//
//     [   sorted   |     unsorted     ]
//
//     [       sorted       | unsorted ]
//
//     [              sorted           ]
//
//
// The two algorithms move in opposite directions,
// but the underlying idea is identical:
//
//     Select the entry that belongs next.
//
//     Move it into its final position.
//
//     Repeat.
//
// This is why both are called selection sort.
//
//
//
// Runtime analysis
//
// Does reversing the direction make this version
// faster?
//
// Suppose the array contains n entries.
//
// On the first pass, we must find the minimum among
//
//     n
//
// entries. This requires
//
//     n - 1
//
// comparisons.
//
// On the second pass, one entry is already in its
// final position, so we search
//
//     n - 1
//
// entries and perform
//
//     n - 2
//
// comparisons.
//
// This continues:
//
//     (n - 1) + (n - 2) + ... + 3 + 2 + 1
//
// comparisons.
//
// Therefore, the total is again
//
//     n(n - 1)
//     ----------
//         2
//
// comparisons.
//
// Thus, just like the previous version, this
// selection sort has runtime
//
//     Theta(n^2).
//
//
//
// Does the initial order matter?
//
// Consider an already sorted array:
//
//     1   2   3   4   5
//
// We still search:
//
//     5 entries,
//     then 4,
//     then 3,
//     then 2.
//
// Now consider a reverse-sorted array:
//
//     5   4   3   2   1
//
// We again search:
//
//     5 entries,
//     then 4,
//     then 3,
//     then 2.
//
// The number of comparisons is the same.
//
// Thus, measured by comparisons, both the best-case
// and worst-case runtimes are
//
//     Theta(n^2).
//
//
//
// Questions:
//
// 1. In the original selection sort, which entry was
//    selected on each pass?
//
// 2. Which entry is selected in this version?
//
// 3. In which direction does the sorted portion grow
//    in the original version?
//
// 4. In which direction does it grow here?
//
// 5. If k entries have already been placed at the
//    beginning of the array, how many entries remain
//    to be searched?
//
// 6. Why must an index returned by
//
//        find_min( array + k, capacity - k )
//
//    be adjusted before it can be used as an index
//    into the original array?
//
// 7. Does changing from selecting maxima to selecting
//    minima change the asymptotic runtime?
//
// 8. If the array is already sorted, does this
//    selection sort perform fewer comparisons?
//
//
//
// The larger lesson:
//
// Two pieces of code can look quite different:
//
//     one works from right to left;
//
//     the other works from left to right;
//
//     one repeatedly selects a maximum;
//
//     the other repeatedly selects a minimum.
//
// Yet both implement the same fundamental algorithmic
// idea and both perform the same order of work.
//
// When analyzing algorithms, we therefore care about
// more than the exact statements in the program.
//
// We care about the underlying method used to solve
// the problem.