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

Hortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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.

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub.  Join the discussion.

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 }}