Insertion sort implementation adapted from the web I've found this implementation on the web:


void insertSort(int a[], int length) 
{  
    int i, j, value;  
    int k=0;
    for(i = 1; i &lt; length; i++) 
    {  
      value = a[i];  
        for (j = i - 1; j &gt;= 0 &amp;&amp; a[j] &gt; value; j--) 
      {  
            a[j + 1] = a[j]; 
            k++;
        }  
        a[j+1] = value;  
    }  

    printf("k=%d", k);
}



I have written this:

#include &lt;stdio.h&gt;

#define SIZE 8

int array1[SIZE] = {77, 33, 44, 11, 88, 22, 66, 55};

void PrintArray()
{
    int i = 0;
    printf("\n");
    for(i=0 ; i&lt;SIZE ; i++)
    {
        printf("%d, ", array1[i]);
    }
}

void Insert(int insertPosition, int insertElementIndex)
{
    int temp = array1[insertElementIndex];
    int i = 0;

    for(i=insertElementIndex ; i&gt;=insertPosition ; i--)
    {
        array1[i] = array1[i-1];
    }

    array1[insertPosition] = temp;
}

void InsertionSort()
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0 ; i&lt;SIZE ; i++)
    {
        for(j=0 ; j&lt;=i ; j++)
        {
            if(array1[i] &lt; array1[j])
            {
                Insert(j, i);               
                PrintArray();               
            }

            k++;
        }
    }
    printf("k=%d", k);
}



main()
{
    PrintArray();

    InsertionSort();
    //insertSort(array1, SIZE);

    PrintArray();

    getch();
}


Is there any problem with this implementation?
First of all, what you implemented is not insertion sort:

Insertion sort uses one loop to iterate over the array, and for each element uses another loop to move the element to its desired location. This makes its running time \$O(n^2)\$.

Your algorithm iterates over each pair of elements (using the two nested loops in InsertionSort()) and then for each pair, uses a third loop (the one in Insert) to move the one element to the position of the other if necessary. This makes its running time \$O(n^3)\$, which is significantly worse than \$O(n^2)\$.

So that's a problem.



In addition to that there's also a major usability problem with your function:

By making the array and its size a global variable and a constant instead of parameters, you make reuse of your function as good as impossible. If you want to use the function to sort multiple arrays, you have to copy each one into the global variable, call the sort function, and then copy it back from the global variable again. And this only works if all the arrays have the same size. If the arrays have different sizes it's plain impossible to use your InsertionSort function on them.

So passing the array and its size as parameters is clearly preferable.



Lastly, I realize that you're most probably aware of this and this is just a learning exercise, but just in case:

In most real-world applications, quick sort or merge sort are usually preferable to insertion sort, having much better performance characteristics than insertion sort in the majority of cases. So if you want to use this in real code, you should rethink whether you really want to use insertion sort.

Also the standard C library has a sort function built-in, so you don't even have to implement anything yourself.