Friday, July 27, 2012

Implementing Insertion sort in C/C++

Below function implements the insertion sort algorithm. The function takes input as a array of integers and size of the array.
The sorting is performed in place. 


void InsertionSort(int * array, int size)
{
    //we are starting from second element of the array
    for(int counter = 1; counter < size; counter++)
    {
        int nKey = array[counter];
        int tempCounter = counter-1;
        while(tempCounter >= 0 && array[tempCounter] > nKey )
        {           
            array[tempCounter+1] = array[tempCounter];
            tempCounter--;
        }
        array[tempCounter+1] = nKey;       
    }
}