Hello Friends, In this series to explain all the sorting algorithms in C#. This is my next article to have the best, easy and clear step by step explanation of Insertion sort algorithm in C# with code example.
Below are the other sorting algorithm I have covered on my blog.
Insertion sort algorithm in C#
Before moving to the code of the algorithm lets understand the concept of Insertion sort algorithm.
And as usual I will explain with the help of an initial array which is not sorted. Suppose I take the array as {5, 3, 4, 7, 2, 8, 6, 9, 1}. The same is present as “Initial Array” in below figure.
Concept of Insertion Sort
Insertion sort is based on the assumption that all the elements present on the left side of element being sorted are already sorted.
We will start with the first element and we will assume that this element is already sorted. And hence we will skip this element.
Next we will move to the second element i.e element at index 1, which is 3.
[Important]Since the elements in left side of the element are already sorted we need to find the appropriate position of this element in the already sorted array. This is difficult to visualize right now as we are only. at second element. Please be with me everything will be clear as we move forward. And we will do this by comparing the current element with the element present on left side of element. If the current element is smaller, we will swap the elements else do nothing.
As shown in the step 1, element 3 and 5 will change their position. As 3 is less than 5.
Now the cursor will move to third element as shown in step 2. Now read the para I have marked as [Important] above. Since out current element 4 is smaller than 5 we will swap the elements. Resulting an sorted array till index 2.
Step 3.Now we will move to next index i.e. 3. The element at index 3 is 7. We will compare the element at just left of the element 7. The element the left of 7 is 5 and since 7 is greater than 5, there is no need to compare rest of the elements as they are already sorted. Hence 7 will retain its position.
Step 4. Now the cursor will move to nest element present at index 4. The element is 2. And when we compare the current element with the immediate left element i.e 7, we have to swap their position since 2 is less than 7.
As you can see in the below figure at Step 4a, 7 is moved to index 4, and 2 is moved to index 3.
Now we will compare 2 with the element present on immediate left i.e. 5. Again 2 is less than 5 we swap their positions. 5 is moved to index 3 and 2 is moved to index 2.
Similarly in step 4b we swap positions of 2 and 4. Finally in step 4c we swap the position of 2 and 3 resulting an array in present in step5.
All the above steps helped to find the position of element 2 which was originally present at index 4.
Now the cursor moves to index 5. And the element present at index 5 is 8. We compare 8 with the element present at the immediate left i.e. 7. Since 8 is greater than 7, they won’t swipe their positions. And no further comparison will take place.
Now the index moves to index 6, the element is also 6. You can see in the above figure step 5 and 5a for the movement of element 6.
I won’t explain further to prevent article from getting verbose. And leave it to reader to figure out movement of elements present at index 7 and 8.
Finally at the end of all the steps we should get an sorted array as {1,2,3,4,5,6,7,8,9}.
Code for Insertion sort algorithm in C#
Before looking at the below code, I will ask the reader to give it a try. It will be a nice experience to write code for this.
If you are stuck, have a look at the below code present in C#. Since Java and C# are almost similar language you can write it into Java as well.
private static void InsertionSort()
{
int[] arr = { 6, 1, 7, 8, 9, 3, 5, 4, 2 };
int pos = 1;
while (pos < arr.Length)
{
//Get the postion of the immediate left element
int leftElement = pos - 1;
//Get the local cursor for moving the current element
int localPos = pos;
while (leftElement > -1 && arr[localPos] < arr[leftElement])
{
//If the current element is less than the immediate left element, swap their locations
if (arr[localPos] < arr[leftElement])
{
arr[leftElement] = arr[leftElement] + arr[localPos];
arr[localPos] = arr[leftElement] - arr[localPos];
arr[leftElement] = arr[leftElement] - arr[localPos];
leftElement--;
localPos--;
}
else
break;
}
pos++;
}
Array.ForEach(arr, (item) => Console.WriteLine(item));
}I hope the code is easily understandable. I am creating a sub array of the sorted elements. And using that array to find the best position of the cursor element.