Introduction
In this article i am going to explain about the Insertion sort algorithm.Insertion Sort is based on the idea of consuming one element from input array in each iteration to find its correct position in sorted array.This algorithm is efficient for smaller datasets.
![Algorithms in C#]()
So first I am going to explain insertion sort algorithm then I will be providing a C# code to execute it.
Please refer to the below links for my earlier blogs on various sorting algorithms in C#
The Insertion Sort Algorithm
Insertion sort compares the current element with largest value in the sorted array. If the current element is smaller then the algorithm finds its correct position in sorted array and moves the element to that position otherwise if the current element is greater then it leaves the element in its place and moves on to next element.
To place the element in its correct position in sorted array, all the elements larger than the current element is shifted one place ahead.Thus the sorted array will grow at each iteration.
Let us understand this with the help of an example.
Let us take input array as : 8 5 7 3 1
The sorted output for this array is : 1 3 5 7 8
|
Iterations
|
Input Array
|
Sorted Array
|
UnSorted Array
|
|
Iteration 1
|
8 5 7 3 1
|
|
8 5 7 3 1
|
|
Iteration 2
|
8 5 7 3 1
|
5
|
8 7 3 1
|
|
Iteration 3
|
5 8 7 3 1
|
5 7
|
8 3 1
|
|
Iteration 4
|
5 7 8 3 1
|
3 5 7
|
8 1
|
|
Iteration 5
|
3 5 7 8 1
|
1 3 5 7
|
8
|
Hence we got the sorted array in iteration 5.
Time Complexity
Every element is compared to every other element of sorted array. Hence complexity of Insertion sort is O(n²).
Conclusion
In this tutorial we learned about the Insertion sort algorithm and its implementation using C#.
Please find the attached code for better understanding.