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.
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.
Every element is compared to every other element of sorted array. Hence complexity of Insertion sort is O(n²).
In this tutorial we learned about the Insertion sort algorithm and its implementation using C#.
You can download the source code from here
Introduction Blazor is a .NET web framework that allows us to create client-side applications using…
Introduction In this article, we are going to create a sudoku solver with the help…
Introduction In this article, we will learn how to implement Azure serverless with Blazor web…
Introduction Angular is an open-source framework that allows us to create applications for multiple platforms…
Introduction In this article, we will create an optical character recognition (OCR) application using Angular…
Introduction In this article, we will create an optical character recognition (OCR) application using Blazor…