Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Insertion Sort Algorithm in C#

DZone's Guide to

Insertion Sort Algorithm in C#

A common sorting algorithm is the Insertion Sort. We take a look at what it is using C# and how it performs.

· Big Data Zone ·
Free Resource

The open source HPCC Systems platform is a proven, easy to use solution for managing data at scale. Visit our Easy Guide to learn more about this completely free platform, test drive some code in the online Playground, and get started today.

In this article, I am going to explain the Insertion Sort algorithm. Insertion Sort is based on the idea of consuming one element from an input array in each iteration to find its correct position in a sorted array. This algorithm is efficient for smaller datasets.

First, I am going to explain the Insertion Sort algorithm. Then, I will provide some C# code to execute it.

The Insertion Sort Algorithm

Insertion Sort compares the current element with the largest value in a sorted array. If the current element is smaller, then the algorithm finds its correct position in the sorted array and moves the element to that position. Otherwise, if the current element is greater, it leaves the element in its place and moves on to the next element.

To place the element in its correct position in a sorted array, all the elements larger than the current element are shifted one place ahead. Thus, the sorted array will grow at each iteration.

Let's understand this with the help of an example.

Let's take the 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 the sorted array. Hence, the complexity of Insertion Sort is O(n²).

Conclusion

In this tutorial, we learned about the Insertion Sort algorithm and its implementation using C#.

You can download the source code from here.

You can find my other articles on algorithms here.

Managing data at scale doesn’t have to be hard. Find out how the completely free, open source HPCC Systems platform makes it easier to update, easier to program, easier to integrate data, and easier to manage clusters. Download and get started today.

Topics:
c# ,big data ,data analytics ,algorithms ,sorted array ,insertion sort ,tutorial

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}