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

// Insertion sort
//
// Selection sort repeatedly selected an entry and
// moved it into its final position.
//
// Insertion sort uses a different idea.
//
// It maintains a sorted portion at the beginning of
// the array:
//
//     [       sorted       | unsorted ]
//
// It then takes the first entry from the unsorted
// portion and inserts it into the correct position
// in the sorted portion.
//
// This is similar to arranging playing cards in your
// hand. When you receive a new card, you move larger
// cards out of the way until you find the correct
// position for the new card.

// Function declarations
int main();

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

void insert(
    double            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.

    insertion_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 );

    insertion_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 );

    insertion_sort( data, N );

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

    // Test an already-sorted array.

    double sorted[6]{
        1.0, 2.0, 3.0, 4.0, 5.0, 6.0
    };

    insertion_sort( sorted, 6 );

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

    // Test a reverse-sorted array.

    double reversed[6]{
        6.0, 5.0, 4.0, 3.0, 2.0, 1.0
    };

    insertion_sort( reversed, 6 );

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

    // Test repeated values.

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

    insertion_sort( repeated, 6 );

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

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

    double single[1]{ 42.0 };

    insertion_sort( single, 1 );

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

    // An empty array is also considered sorted.

    insertion_sort( nullptr, 0 );

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

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

    return 0;
}


// void insertion_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
//     The first entry by itself is already sorted.
//
//     Beginning with the second entry, repeatedly
//     consider one additional entry.
//
//     Before each call to insert(...), the entries
//
//         array[0], ..., array[k - 2]
//
//     are sorted.
//
//     The function insert(...) takes
//
//         array[k - 1]
//
//     and inserts it into the appropriate position
//     among those sorted entries.
//
//     Afterward, the first k entries are sorted.
//
//     Continue until all entries are sorted.

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

    for ( std::size_t k{ 2 };
          k <= capacity;
          ++k ) {
        insert( array, k );
    }

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


// void insert( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
//
// @param array
//     An array of doubles in which all but the last
//     entry are assumed to be sorted.
//
// @param capacity
//     The number of entries in the array.
//     This must be positive.
//
// @precondition
//     The first capacity - 1 entries are sorted.
//
// @algorithm
//     Store the final entry in a temporary variable.
//
//     Starting at the end of the sorted portion,
//     move entries greater than this value one
//     position to the right.
//
//     Continue until either:
//
//       - the beginning of the array is reached, or
//
//       - the preceding entry is less than or equal
//         to the value being inserted.
//
//     This creates an empty position into which the
//     value can be placed.

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

    double const value{ array[capacity - 1] };

    std::size_t k{ capacity - 1 };

    while ( (k > 0)
         && (array[k - 1] > value) ) {
        array[k] = array[k - 1];
        --k;
    }

    array[k] = value;

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


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









































// How does insertion sort work?
//
// Consider:
//
//     index:   0   1   2   3   4
//
//     value:   4   1   7   3   5
//
// A single entry by itself is already sorted:
//
//              4 | 1   7   3   5
//              -
//            sorted
//
//
// Insert 1.
//
// Save the 1:
//
//     value = 1
//
// Since 4 > 1, move 4 one position to the right:
//
//              _   4 | 7   3   5
//
// Insert 1 into the empty position:
//
//              1   4 | 7   3   5
//              -----
//              sorted
//
//
// The next value is 7.
//
// Since
//
//     4 <= 7,
//
// nothing has to move:
//
//              1   4   7 | 3   5
//              ---------
//                sorted
//
//
// Now insert 3.
//
// Save:
//
//     value = 3
//
// First:
//
//              1   4   7   _ | 5
//                      |
//                      +------> move 7
//
// giving:
//
//              1   4   _   7 | 5
//
// Then:
//
//              1   4   _   7 | 5
//                  |
//                  +------> move 4
//
// giving:
//
//              1   _   4   7 | 5
//
// Since
//
//     1 <= 3,
//
// stop moving entries and insert 3:
//
//              1   3   4   7 | 5
//              -------------
//                  sorted
//
//
// Finally, insert 5:
//
//              1   3   4   7   _
//                          |
//                          +----> move 7
//
// and then:
//
//              1   3   4   _   7
//
// Since
//
//     4 <= 5,
//
// insert 5:
//
//              1   3   4   5   7
//
// The entire array is now sorted.
//
//
//
// The key idea
//
// Insertion sort maintains this situation:
//
//     [       sorted       | unsorted ]
//                            ^
//                            |
//                         next value
//
// It removes the next value conceptually, shifts
// larger entries to the right, and inserts the value
// into the resulting space:
//
//     [       sorted       | unsorted ]
//
//                  |
//                  v
//
//     [    sorted    |     unsorted   ]
//
//                  |
//                  v
//
//     [      sorted      |  unsorted  ]
//
// The sorted portion grows by one entry on each pass.
//
//
//
// How is this different from selection sort?
//
// Selection sort:
//
//     searches the unsorted portion for the entry
//     that belongs next.
//
// Insertion sort:
//
//     takes the next entry and determines where it
//     belongs in the sorted portion.
//
// Selection sort:
//
//     [ sorted |          unsorted          ]
//                   search for minimum
//                   ---------------->
//
// Insertion sort:
//
//     [          sorted          | unsorted ]
//                                 ^
//                                 |
//                         take this entry and
//                         move it to the left
//
// Both gradually construct a sorted array, but they
// do so in different ways.
//
//
//
// Runtime: the best case
//
// Consider an array that is already sorted:
//
//     1   2   3   4   5   6
//
// When 2 is considered:
//
//     1 <= 2
//
// so nothing moves.
//
// When 3 is considered:
//
//     2 <= 3
//
// so nothing moves.
//
// The same is true for every subsequent entry.
//
// Each pass requires only a small, constant amount
// of work.
//
// There are approximately n passes.
//
// Therefore, insertion sort has best-case runtime
//
//     Theta(n).
//
// This is already different from the selection sort
// we studied.
//
// Selection sort still searches the entire remaining
// portion even if the array is already sorted.
//
// Its best-case runtime remains
//
//     Theta(n^2).
//
//
//
// Runtime: the worst case
//
// Now consider a reverse-sorted array:
//
//     6   5   4   3   2   1
//
// When inserting 5, one entry must move:
//
//     1 move
//
// When inserting 4, two entries must move:
//
//     2 moves
//
// When inserting 3:
//
//     3 moves
//
// Then:
//
//     4 moves
//
// and finally:
//
//     5 moves.
//
// The total is:
//
//     1 + 2 + 3 + 4 + 5.
//
// In general, for n entries:
//
//     1 + 2 + 3 + ... + (n - 1)
//
// which equals:
//
//     n(n - 1)
//     ----------
//         2
//
// Thus, in the worst case, the amount of work grows
// quadratically.
//
// The worst-case runtime is therefore
//
//     Theta(n^2).
//
//
//
// Best case versus worst case
//
//                         best          worst
//                         case           case
//     ------------------------------------------------
//
//     selection sort     Theta(n^2)     Theta(n^2)
//
//     insertion sort     Theta(n)       Theta(n^2)
//
// This is an important difference.
//
// Insertion sort can take advantage of an array that
// is already sorted or nearly sorted.
//
//
//
// What does "nearly sorted" mean?
//
// Consider:
//
//     1   2   3   5   4   6   7   8
//
// Only 5 must move:
//
//     1   2   3   5   4   6   7   8
//                 <---
//
// resulting in:
//
//     1   2   3   4   5   6   7   8
//
// Very little work is required.
//
// Compare that with:
//
//     8   7   6   5   4   3   2   1
//
// Here, almost every new entry must move past almost
// every entry already in the sorted portion.
//
// Thus, insertion sort's actual amount of work depends
// strongly on how far the original array is from
// being sorted.
//
//
//
// A useful visual comparison
//
// Already sorted:
//
//     1  2  3  4  5  6  7  8
//
//     ---------------------------------------->
//                 very little movement
//
//
// Nearly sorted:
//
//     1  2  3  5  4  6  7  8
//              <-
//
//     ---------------------------------------->
//                  little movement
//
//
// Reverse sorted:
//
//     8  7  6  5  4  3  2  1
//
//     <---------------------------------------
//     <---------------------------------
//     <---------------------------
//     <---------------------
//     <---------------
//     <---------
//     <---
//
//                 much more movement
//
//
//
// Questions:
//
// 1. Why can insertion sort begin with the second
//    entry rather than the first?
//
// 2. Before insert(array, k) is called, what do we
//    know about the first k - 1 entries?
//
// 3. Why must larger entries be shifted to the right
//    before the new value is inserted?
//
// 4. What happens when the new value is already
//    greater than or equal to the previous entry?
//
// 5. What is the best possible arrangement of the
//    original array for insertion sort?
//
// 6. What is the worst possible arrangement?
//
// 7. Why does an already-sorted array require
//    Theta(n) work rather than Theta(n^2) work?
//
// 8. Why does a reverse-sorted array require
//    Theta(n^2) work?
//
// 9. Why can insertion sort be preferable to
//    selection sort when an array is already nearly
//    sorted?
//
//
//
// --------------------------------------------------
// An advanced observation
// --------------------------------------------------
//
// The following idea is NOT something you need to
// understand yet.
//
// It belongs more naturally in a second-year course
// on algorithms and data structures.
//
// It does, however, give us a more precise way to
// describe why insertion sort is fast on nearly
// sorted arrays.
//
//
//
// Inversions
//
// An inversion is a pair of entries that occur in
// the wrong relative order.
//
// More formally, indices i and j form an inversion
// when
//
//     i < j
//
// but
//
//     array[i] > array[j].
//
// For example:
//
//     1   2   4   3   5
//
// contains one inversion:
//
//     4   3
//
// because 4 occurs before 3 even though 4 > 3.
//
//
//
// Consider:
//
//     3   1   2
//
// The inversions are:
//
//     3   1
//
// and
//
//     3   2.
//
// Thus, this array has two inversions.
//
//
//
// A sorted array:
//
//     1   2   3   4   5
//
// has
//
//     d = 0
//
// inversions.
//
// A reverse-sorted array:
//
//     5   4   3   2   1
//
// has as many inversions as possible:
//
//     d = n(n - 1)/2.
//
//
//
// Why are inversions interesting for insertion sort?
//
// Look again at the inner loop:
//
//     while ( (k > 0)
//          && (array[k - 1] > value) ) {
//         array[k] = array[k - 1];
//         --k;
//     }
//
// Every time an entry moves one position to the
// right, the value being inserted moves past one
// entry that was greater than it.
//
// In other words, one inversion is being removed.
//
// Therefore:
//
//     one shift <----> one inversion removed.
//
// Over the entire execution of insertion sort, the
// number of these shifts is exactly the number of
// inversions in the original array.
//
// If we call that number d, the work can be described
// more precisely as:
//
//     Theta(n + d).
//
// You may also see this written more loosely as:
//
//     O(n + d).
//
//
//
// Why n + d?
//
// The n represents the basic work of stepping through
// the array.
//
// The d represents the additional work required to
// move entries past one another.
//
// Thus:
//
//     already sorted:
//
//         d = 0
//
//         Theta(n + 0)
//         = Theta(n)
//
//
//
//     nearly sorted:
//
//         d is small
//
//         Theta(n + d)
//
//         still close to linear
//
//
//
//     reverse sorted:
//
//         d = n(n - 1)/2
//
//         Theta(n + n^2)
//         = Theta(n^2)
//
//
//
// This one expression therefore explains both the
// best case and the worst case:
//
//                  d
//                  |
//                  v
//
//     Theta( n + d )
//
//        |       |
//        |       +---- disorder already present
//        |
//        +------------ basic pass through the array
//
//
// Again, this inversion analysis is advanced.
//
// At a first-year level, the important conclusions
// are simply:
//
//     best case:       Theta(n)
//
//     worst case:      Theta(n^2)
//
//     nearly sorted:   often much faster than the
//                      worst case.
//
// In a second-year algorithms course, the idea of
// inversions gives us the more precise statement:
//
//     Theta(n + d),
//
// where d is the number of inversions in the original
// array.
//
// This is an example of a deeper kind of algorithm
// analysis: instead of describing the runtime using
// only the SIZE of the input, we can also describe
// it using a property of the input itself.