Navigation

Related Articles

Back to Latest Articles

How To Make Insertion Sort Algorithm In C# – Made Easy

Insertion sort is one of the simplest sorting algorithms for sorting single dimensional arrays of various different data types.


Andraz Krzisnik
How To Make Insertion Sort Algorithm In C#...

Insertion sort is just another algorithm with which we can sort single dimensional arrays. Similarly to selection sort, it is also one of the simplest algorithms to sort objects in accending or decending order. Therefore, it also doesn’t score any higher in efficiency.

We begin the same way as with selection sort by dividing into 2 parts, namely sorted and unsorted. However, with insertion sort, we need to leave the first object of the array in the sorted part of the array. Furthermore, it’s going to serve as a reference point when we start with our first iteration.

With each iteration, the algorithm picks the first element in the unsorted part of the array and inserts it in a suitable position in the sorted part. In order to sort the entire array, we iterate this operation as many times until the unsorted part is empty.

Insertion sort in C#

Let’s first take a look at the code to get a better understanding of how it actually works.

public static class InsertionSort
    {
        public static void Sort<T>(T[] array) where T : IComparable
        {
            for (int i = 1; i < array.Length; i++)
            {
                int j = i;
                while (j > 0 && array[j].CompareTo(array[j - 1]) < 0)
                {
                    Swap(array, j, j - 1);
                    j--;
                }
            }
        }

        private static void Swap<T>(T[] array, int first, int second)
        {
            T temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }
    }

First of all, we create a static class for the insertion sort, which contains 2 methods. Swap method is a private method, which we use only inside the class. The sort method is where all the work gets done. Furthermore, it accepts 1 parameter, which is the array we want to sort.

The Sort method also accepts arrays of different data type, which makes it convenient for reuse. In detail, we accomplished this by using the IComparable interface and its method CompareTo.

As you can see, we start by creating a for loop to iterate through the whole array. The variable i is set to 1, because we will skip the first element, since it already belongs to the sorted part.

Next, we nest a while loop inside, which will loop through the entire sorted part and find the correct place for an object. In other words, for loop loops forward, while while loop propagates backwards.

Conclusion

Thank you for visiting this post about implementation of insertion sort in C# and I hope you found it useful.

You can also download the demo project and try it out yourself.

Show Comments (0)

Comments

Related Articles

Morphological Processes

How To Make Thinning In Image Processing Work With C#

Thinning is a morphological operation in image processing, which eats away at the foregorund pixels and leaves only lines shaping objects.

Posted on by Andraz Krzisnik
Tone and Color Corrections

How To Adjust Image Tone – C# Guide

This guide shows how to apply image tone corrections for flat, dark and light images. The purpose of it is to adjust brightness and contrast.

Posted on by Andraz Krzisnik