Performing insertion sort in C#

Question

This is my code in C# for performing insertion sort:

static int[] performInsertionSort(int[] inputarray)
{
    for (int i = 0; i < inputarray.Length-1; i++)
    {
        int j = i+1;

        while (j>0)
        {
            if (inputarray[j-1] > inputarray[j])
            {
                int temp = inputarray[j-1];
                inputarray[j - 1] = inputarray[j];
                inputarray[j] = temp;

            }
            j--;
        }
    }
    return inputarray;
}

Is there a way to optimize this code? Can I make further changes to it?

Answer 1

Your sorting logic is dependent upon the specific type.

"Separate your data representation from logic." you must take advantage of the generic to reuse the same component to sort any kind of object. In case of class you can specify comparer to sort the values.

Naming convention should be followed. i and j does not make sense and in c# standard method naming convetion should Pascal case , should not start with lowercase.

Rest logic looks good.

public static T[] PerformInsertionSort<T>(T[] inputarray, Comparer<T> comparer=null)
    {
        var equalityComparer = comparer ?? Comparer<T>.Default;
        for (var counter = 0; counter < inputarray.Length - 1; counter++)
        {
            var index = counter + 1;
            while (index > 0)
            {
                if(equalityComparer.Compare(inputarray[index - 1],inputarray[index])>0)
                {
                    var temp = inputarray[index - 1];
                    inputarray[index - 1] = inputarray[index];
                    inputarray[index] = temp;
                }
                index--;
            }
        }
        return inputarray;
    }

Answer 2

While kyles and paritosh code should preform a sort, the code is not a true Insertion Sort and is not as efficient as a true Insertion Sort. The problem is that in your versions the inner loop has to proceed until j == 0 where as with the real Insertion Sort, the inner loop terminates as soon as the condition (inputArray[j-1] > inputArray[j]) is no longer true. Another way of thinking about it is that that once the inner loop has moved a value to its optimum position in the array, the loop can terminate without having to do the remaining compares. If the initial array is randomly distributed, a true Insertion Sort only has to do about half the number of compares as your algorithms. And if the initial array is already nearly sorted, a true Insertion Sort will only have to do slightly more than N compares where as your algorithms will have to do about N squared compares. A true Insertion Sort looks like this:

static int[] performInsertionSort(int[] array)
{
    int length = array.Length;

    for (int i = 1; i < length; i++)
    {
        int j = i;

        while ((j > 0) && (array[j] < array[j - 1]))
        {
            int k = j - 1;
            int temp = array[k];
            array[k] = array[j];
            array[j] = temp;

            j--;
        }
    }
    return array;
}

Answer 3

From your code:

static int[] performInsertionSort(int[] inputarray)
{
    for (int i = 0; i < inputarray.Length-1; i++)
    {
        int j = i+1;

       while (j>0)
        {
            if (inputarray[j-1] > inputarray[j])
            {
                int temp = inputarray[j-1];
                inputarray[j - 1] = inputarray[j];
                inputarray[j] = temp;

           }
            j--;
        }
    }
    return inputarray;
}

I can see a couple of things that I would do differently.

Instead of using a while on the inside I would probably use another for loop because it would look a little bit cleaner. I would also change the name of inputarray to inputArray because of common naming schemes.

Personally I think for something this simple i and j are fine, if the operations become more complex and you aren't just sorting random numbers, then you would have something meaningful that you could name them, so I would just keep i and j.

Here is what my version would look like:

static int[] performInsertionSort(int[] inputArray)
{
    for (int i = 0; i < inputArray.Length-1; i++)
    {
        for (int j = i + 1; j > 0; j--)
        {
            if (inputArray[j-1] > inputArray[j])
            {
                int temp = inputArray[j-1];
                inputArray[j-1] = inputArray[j];
                inputArray[j] = temp;
            }
        }
    }
    return inputArray;
}

---

I wanted to test this to make sure that it worked correctly, here is my code with the output programmed into the application.

Insertion sort revised with output to console