7
\$\begingroup\$

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?

\$\endgroup\$
1
11
\$\begingroup\$

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;
    }
\$\endgroup\$
10
  • 1
    \$\begingroup\$ Making it type-independent results in quite heavy hit in performance. For array of 65535 random integers Kyle sort took ~10k milliseconds, your <T>Sort jumped to ~19k... and Array.Sort is evil and needed just 5ms (but its basically native quicksort implementation so its not fair to compare with it) \$\endgroup\$
    – PTwr
    Aug 14 '14 at 9:22
  • 3
    \$\begingroup\$ How is counter and index any better than i and j? \$\endgroup\$
    – svick
    Aug 14 '14 at 11:02
  • \$\begingroup\$ @svick , better meaning is good rather i and j. it could be anything better which you want \$\endgroup\$
    – Paritosh
    Aug 14 '14 at 11:04
  • 9
    \$\begingroup\$ @PTwr In general, I agree. But my question was very specific: how are the proposed names counter and index, which also don't say anything about what or why are they counting better than i and j? People know that it's common to use i as loop counter and j if you need a second one. But counter and index would confuse me, because I don't see any meaning behind those names (except that they're also probably loop counters). \$\endgroup\$
    – svick
    Aug 14 '14 at 12:48
  • 3
    \$\begingroup\$ @Snowbody "Is there a way to optimize this code?" - Performance is of concern as it is main part of optimization. \$\endgroup\$
    – PTwr
    Aug 16 '14 at 18:41
9
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • \$\begingroup\$ you don't need to have a separate variable 'k' and you could just refer to array.length rather than having a separate variable 'length'. (if anything length should be a constant rather than a variable).. but fine.. \$\endgroup\$
    – barlop
    Aug 29 '16 at 7:04
  • \$\begingroup\$ I like it. But also here's an interesting variation which does a right shift with a swap (and the right shift involves swaps of course). stackoverflow.com/questions/29576228/… \$\endgroup\$
    – barlop
    Aug 29 '16 at 7:06
5
\$\begingroup\$

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

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.