#include <stdio.h>

void exchange(int* array, int p1, int p2)
{
    if (p1 == p2)
        return;
    int temp = array[p1];
    array[p1] = array[p2];
    array[p2] = temp;
}

void insertSort(int* array, int len)
{
    int sorted = 0; //the 1st data we think was already sorted
    int cur;
    for (cur = 1; cur < len; cur++)//start from 2nd data
    {
        //loop with sorted range
        int sort;
        for (sort = 0; sort <= sorted; sort++)
        {
            if (array[cur] <= array[sort])
            {
                // let current data move forward one by one and stop at right postion
                int curPos = cur;
                while (curPos != sort)
                {
                    exchange(array, curPos, curPos - 1);
                    curPos--;
                }
                break;
            }
        }
        sorted++;
    }
}

//From Intruduction Of Alogrithim
void insertSort1(int* array, int len)
{
    for (int i = 1; i < len; i++)//loop start from 2nd data cause we think 1st is already sorted
    {
        int key = array[i];//current data we call it key
        int j = i - 1;//watch pre data of key
        while (j >= 0 && array[j] > key)
        {
            array[j+1] = array[j];//if pre data bigger, move to right
            j--;//if pre data stiill bigger than key, move to right
        }//end while for moving
        array[j + 1] = key;// when move over the postion `j+1` was empty insert the key
    }    
}

void main()
{
    intarray[10] = { 1, 8, 3, 6, 2, 4, 7, 5, 9, 0 };
    printf("before:");
    int i;
    for (i = 0; i <= sizeof(array) - 1; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    insertSort(array, sizeof(array));
    printf("\n after:");
    for (i = 0; i <= sizeof(array) - 1; i++)
    {
        printf("%d ", array[i]);
    }
    return;
}