Insertion sort implementation adapted from the web

Question

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 < length; i++) 
    {  
      value = a[i];  
        for (j = i - 1; j >= 0 && a[j] > value; j--) 
      {  
            a[j + 1] = a[j]; 
            k++;
        }  
        a[j+1] = value;  
    }  

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

I have written this:

#include <stdio.h>

#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<SIZE ; i++)
    {
        printf("%d, ", array1[i]);
    }
}

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

    for(i=insertElementIndex ; i>=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<SIZE ; i++)
    {
        for(j=0 ; j<=i ; j++)
        {
            if(array1[i] < 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?

Answer 1

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.

Answer 2

Do not use global variables:

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

This will make your code harder to maintain and more prone to bugs bugs because it can be modified from any point in the program.

Instead, initialize it in main() and pass it to any needed functions. This practice of using local objects over global ones should be followed in all of your programs. However, if you're working with constants, it's okay to keep them global because they're already immutable.

This could also be helpful in case you decide to add additional arrays as it would be easier to maintain them all in main(). Although you could instead make them constants and use local copies, you would still have to avoid returning a local array (undefined behavior). Specifically, you cannot return an array itself because C only returns pointers to arrays, and that pointer will point to local data.

Side-note: remove the commented-out line in main(). It clutters the code a bit, and it's a pointless line even if it remained (SIZE is already global).