//* Insertion Sort Algorithm Demo *
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cassert>
using namespace std;

void RandomizeVec   (int V[], int len);
void PrintVec (const int V[], int len);
void InsertionSort  (int V[], int len);

int main() {
    int n;
    cout << "n= "; cin >> n;
    assert(n>5);
    int*  A = new int[n];
    RandomizeVec(A, n);
    PrintVec(A, n);
    cout << endl << endl;
    InsertionSort(A, n);
    PrintVec(A, n);
    delete A;
    return(0);
}

void RandomizeVec(int V[], int len) {
    time_t TimeInSeconds;
    time( &TimeInSeconds );
    srand((unsigned int)TimeInSeconds);
    for (int i=0; i<len; i++) V[i]=rand();
}

void PrintVec (const int V[], int len) {
    for(int i=0; i<len; i++) {
        cout << setw(7) << V[i];
        if (i%10==9) cout << endl; else cout << " ";
    }
    cout << endl;
}

//===========================================
void InsertionSort(int V[], int len) {
    for (int i=1; i<len; i++) {
        int elem=V[i]; // next element to be inserted
        int    j=i-1;
        while (j>=0 && elem<V[j]) {
            // move sorted elements until the right place
            // to insert elem or begin of array is reached
            V[j+1]=V[j];
            j--;
        }
        V[j+1]=elem;
    }
}