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

// Five selection sorts
//
// Each of the following functions appears to implement
// selection sort.
//
// Some work correctly. Others contain one or more bugs.
//
// For each implementation:
//
//     1. Determine whether or not it correctly sorts
//        every array of doubles.
//
//     2. If it does not, identify the bug.
//
//     3. Find a small array that demonstrates the bug.
//
//     4. Explain how the implementation could be fixed.
//
// Do not assume that successfully sorting the test
// array below proves that an implementation is
// correct.
//
// A test can demonstrate the presence of a bug.
//
// It cannot, by itself, demonstrate the absence of
// all bugs.

// Function declarations
int main();

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

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

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

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

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

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

void copy_array(
    double      const source[],
    double            destination[],
    std::size_t const capacity
);

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

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

    double const original[N]{
        2.8, 8.4, 6.2, 6.5, 1.9,
        7.5, 0.9, 2.0, 9.9, 6.3
    };

    double test_array[N];

    std::cout << "Original:         ";
    print_array( original, N );

    copy_array( original, test_array, N );
    selection_sort_1( test_array, N );
    std::cout << "selection_sort_1: ";
    print_array( test_array, N );

    copy_array( original, test_array, N );
    selection_sort_2( test_array, N );
    std::cout << "selection_sort_2: ";
    print_array( test_array, N );

    copy_array( original, test_array, N );
    selection_sort_3( test_array, N );
    std::cout << "selection_sort_3: ";
    print_array( test_array, N );

    copy_array( original, test_array, N );
    selection_sort_4( test_array, N );
    std::cout << "selection_sort_4: ";
    print_array( test_array, N );

    copy_array( original, test_array, N );
    selection_sort_5( test_array, N );
    std::cout << "selection_sort_5: ";
    print_array( test_array, N );

    return 0;
}


// Version 1

void selection_sort_1(
    double            array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ capacity - 1 };
          k > 0;
          --k ) {
        std::size_t const max_index{
            find_max( array, k )
        };

        if ( array[max_index] > array[k] ) {
            std::swap(
                array[max_index],
                array[k]
            );
        }
    }
}


// Version 2

void selection_sort_2(
    double            array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ capacity - 1 };
          k > 0;
          --k ) {
        std::size_t const max_index{
            find_max( array, k )
        };

        if ( array[max_index] > array[k] ) {
            array[max_index] = array[k];
            array[k] = array[max_index];
        }
    }
}


// Version 3

void selection_sort_3(
    double            array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 };
          k < capacity;
          ++k ) {
        std::size_t index{ k };

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

        double const tmp{ array[index] };
        array[index] = array[k];
        array[k] = tmp;
    }
}


// Version 4

void selection_sort_4(
    double            array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ capacity - 1 };
          k > 0;
          --k ) {
        std::size_t index{ 0 };

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

        if ( array[index] > array[k] ) {
            std::swap(
                array[index],
                array[k]
            );
        }
    }
}


// Version 5

void selection_sort_5(
    double            array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ capacity - 1 };
          k > 0;
          --k ) {
        std::size_t const max_index{
            find_max( array, k )
        };

        if ( array[max_index] > array[k] ) {
            int const tmp{ static_cast<int>(
                array[max_index]
            ) };

            array[max_index] = array[k];
            array[k] = tmp;
        }
    }
}


// std::size_t find_max( ... )
//
// Return the index of the first occurrence of the
// maximum entry among the first capacity entries.
//
// Precondition:
//
//     capacity >= 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;
}


// void copy_array( ... )

void copy_array(
    double      const source[],
    double            destination[],
    std::size_t const capacity
) {
    assert(
        (capacity == 0)
     || ((source != nullptr)
      && (destination != nullptr))
    );

    for ( std::size_t k{ 0 };
          k < capacity;
          ++k ) {
        destination[k] = source[k];
    }
}


// void print_array( ... )

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

    if ( capacity > 0 ) {
        std::cout << array[0];

        for ( std::size_t k{ 1 };
              k < capacity;
              ++k ) {
            std::cout << ", " << array[k];
        }
    }

    std::cout << std::endl;
}









































// Things to investigate
//
// Do not stop when one of the functions successfully
// sorts the array in main().
//
// Try to understand what each function is actually
// doing.
//
// For each version, ask:
//
//     What portion of the array is being searched?
//
//     Is the correct entry being selected?
//
//     Is that entry moved to the correct position?
//
//     Are any values accidentally changed or lost?
//
//     What happens with non-integer values?
//
//     What happens with very small arrays?
//
//
//
// 1. Check the range being searched
//
// Recall that
//
//     find_max( array, capacity )
//
// examines the entries
//
//     array[0]
//     array[1]
//     ...
//     array[capacity - 1].
//
// Therefore:
//
//     find_max( array, k )
//
// examines
//
//     array[0] through array[k - 1],
//
// while
//
//     find_max( array, k + 1 )
//
// examines
//
//     array[0] through array[k].
//
// That difference of one is worth examining very
// carefully.
//
//
//
// 2. Check every swap
//
// A swap must preserve BOTH original values.
//
// Suppose:
//
//     a = 3
//     b = 7
//
// After a correct swap:
//
//     a = 7
//     b = 3
//
// Trace each statement in any code that attempts to
// perform a swap manually.
//
// Ask:
//
//     At any point, was one of the original values
//     overwritten before it was saved?
//
//
//
// 3. Check the type of every temporary variable
//
// The arrays contain doubles.
//
// Suppose an entry contains:
//
//     8.4
//
// What happens if that value is temporarily stored
// in an int?
//
//     double             int
//
//       8.4  ---------->  8
//
// Information has been lost.
//
// Once that fractional part has disappeared, assigning
// the value back to a double does not restore it:
//
//     int               double
//
//      8   ---------->   8.0
//
// Thus, a sorting algorithm can put values in the
// correct relative order and STILL be incorrect if
// it changes the values being sorted.
//
// A sorting algorithm must rearrange the original
// entries.
//
// It must not silently alter them.
//
//
//
// 4. Check which part is supposed to be sorted
//
// For the right-to-left selection sort, we repeatedly
// have:
//
//     [       unsorted       | sorted ]
//                              ^
//
// The entry placed immediately before the vertical
// line must be the maximum of the UNSORTED portion.
//
// Thus, when k is the position being filled, ask:
//
//     Which indices are still unsorted?
//
//     Which indices should be searched?
//
//     Which indices should no longer be touched?
//
//
//
// 5. One version works in the opposite direction
//
// A selection sort does not have to select maxima
// from left to right.
//
// It can instead select minima:
//
//     [ sorted |       unsorted       ]
//              ^
//
// On each pass, find the minimum of the remaining
// unsorted entries and place it at the left-hand
// boundary.
//
// Therefore, code that looks quite different from
// the original selection_sort(...) may still be a
// perfectly valid selection sort.
//
// Do not judge an implementation by whether it
// resembles the original code.
//
// Judge it by what it actually does.
//
//
//
// Finding counterexamples
//
// When you believe an implementation is incorrect,
// try to find the SMALLEST array that demonstrates
// the problem.
//
// Small counterexamples are usually much easier to
// understand than large ones.
//
// Useful possibilities include:
//
//     { 2.0, 1.0 }
//
//     { 1.0, 2.0 }
//
//     { 3.0, 1.0, 2.0 }
//
//     { 1.5, 0.5 }
//
//     { 2.8, 1.9 }
//
//     { 2.0, 2.0 }
//
//
//
// Why are small counterexamples useful?
//
// Suppose a ten-entry array produces:
//
//     0.9, 1.9, 2.0, 2.8, 6.2,
//     6.3, 6.5, 7.5, 8.4, 9.9
//
// or perhaps something that is almost correct.
//
// It may take some effort to determine exactly what
// went wrong.
//
// With:
//
//     { 2.8, 1.9 }
//
// there are very few operations to trace.
//
// This makes the bug much easier to isolate.
//
//
//
// Testing versus proving
//
// Suppose selection_sort_3(...) correctly sorts:
//
//     { 2.8, 8.4, 6.2, 6.5, 1.9,
//       7.5, 0.9, 2.0, 9.9, 6.3 }
//
// What have we established?
//
// Only that it correctly sorted THAT array.
//
// We have not established that it correctly sorts
// every possible array.
//
// Testing can be extremely useful for finding bugs:
//
//     input
//       |
//       v
//     program
//       |
//       v
//     incorrect output
//
// One incorrect result is enough to prove that an
// implementation is incorrect.
//
// However:
//
//     many correct results
//
// do not constitute a proof that the implementation
// is always correct.
//
//
//
// Questions:
//
// 1. Which implementations correctly sort the given
//    ten-entry array?
//
// 2. Which implementations fail on that array?
//
// 3. For every incorrect implementation, can you
//    find a smaller counterexample?
//
// 4. Does find_max(array, k) examine array[k]?
//
// 5. What is the difference between
//
//        find_max( array, k )
//
//    and
//
//        find_max( array, k + 1 )?
//
// 6. What happens if a double is temporarily stored
//    in an int?
//
// 7. Can an algorithm produce an array that is sorted
//    but nevertheless be incorrect?
//
// 8. Which implementation grows the sorted portion
//    from left to right rather than right to left?
//
// 9. Does that make it a different sorting algorithm,
//    or is it still selection sort?
//
// 10. Why is one counterexample sufficient to show
//     that an implementation is not correct?
//
//
//
// A final thought:
//
// Debugging an algorithm is not just asking:
//
//     "Did this program produce the output I wanted?"
//
// A more useful question is:
//
//     "Why must this algorithm produce the correct
//      output for EVERY valid input?"
//
// That shift from testing examples to reasoning about
// all possible inputs is one of the first steps from
// programming toward the study of algorithms.