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.
So first I am going to explain insertion sort algorithm then I will be providing a C# code to execute it.
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²).
See Also
- Bubble Sort Algorithm In C#
- Quick Sort Algorithm In C#
- Merge Sort Algorithm In C#
- Selection Sort Algorithm In C#
- Searching Algorithms In C#
Conclusion
In this tutorial we learned about the Insertion sort algorithm and its implementation using C#.
You can download the source code from here
