// Example 1-12 Insertion sort

#include <iostream>
using namespace std;

//    Function prototypes
void insertion_sort(int* list, int size);
void print(int* a, int size);

int main()
{
    int array[] = { 7,9,6,2,5,3 };
    int size = sizeof (array) / sizeof (int);
    insertion_sort(array, size);
    print(array, size);
    return 0;
}

void insertion_sort(int* list, int size)
{
    int i, j;       // for loop indexes
    int valueToBeInserted;
    bool found;     // flag to indicate insert position found

    for (i = 1; i < size; i++)
    {
        // The ith element will be inserted into the "sorted" list in the correct location
        found = false;
        // valueToBeInserted will hold the ith element in the "unsorted list
        valueToBeInserted = list[i];

        // find the position in sorted list for insertion
        for (j = i - 1; j >= 0 && !found;)
        {
            // if valueToBeInserted < the jth element, shift unsorted elements (to the right)
            if (valueToBeInserted < list[j])
            {
                list[j + 1] = list[j];
                j--;
            }
            // otherwise the insertion position is found
            else
            {
                found = true;
            }
        }
        // insert valueToBeInserted into its correct position in the sorted list
        list [j + 1] = valueToBeInserted;
    }
}

void print(int* a, int size)
{
    int i;
    for (i = 0; i < size; i++)
    {
        cout << a[i] << '\t';
    }
    cout << endl;
}