// insertion.cpp - insertion sort demo
// cmc, 5/22/2010

#include <iostream>
using namespace std;

// insertion sort for integer array
void sort(int a[], int n) {
    
    for (int i=1; i<n; i++) {
        int key = a[i];
        int j = i;
        bool more = a[j-1] > key;

        while(more) {
            a[j] = a[j-1]; // move a[j-1] one space right
            j--;
            more = (j > 0) ? (a[j-1] > key) : 0;
        }
        a[j] = key;
    }
}

// utility print function for integer array
void pr(int a[], int n) {
    for (int i=0; i<n; i++)
        cout << " " << a[i];
    cout << endl;
}

// simple main
int main() {
    int x[] = {72, 91, 4, 13, 7, 6, 50, 25, 44, 1};
    int n = 10;
    cout << "before sorting:";
    pr(x,n);
    sort(x,n);
    cout << "after sorting:";
    pr(x,n);
    return 0;
}