Insertion Sort – Part 2 – Hackerrank Challenge – C# Solution
This is the c# solution for the Hackerrank problem – Insertion Sort – Part 2 – Hackerrank Challenge – C# Solution.
Source – Ryan Fehr’s repository.
/*
Problem: https://www.hackerrank.com/challenges/insertionsort2/problem
C# Language Version: 7.0
.Net Framework Version: 4.7
Tool Version : Visual Studio Community 2017
Thoughts :
1. Let the unsorted array be arr and number of elements in arr be n.
2. Initialize a counter c with 1.
3. Start a loop until c < n
3.1 Let the element to be sorted in current pass is e located at cth index of arr.
3.2 Initialize a counter j = c-1.
3.3 Start a loop
3.3.1 if e < arr[j] then set arr[j + 1] = arr[j].
3.3.2 if e >= arr[j] then break the loop.
3.3.3 decrement j by 1.
3.3.4 Keep repeating steps from 3.3.1 through 3.3.3 untill loop breaking condition isn't met.
3.4 j+1 is the correct position where e needs to be inserted. Replace (j+1)th element of array with e.
3.5 Increment c by 1.
3.6 Keep repeating steps from 3.1 through 3.5 untill loop breaking condition isn't met.
Time Complexity: O(n^2) //There is a nested loop.
Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
*/
using System;
class Solution
{
static void Insert(int[] arr, int i)
{
var currElement = arr[i];
var j = i - 1;
for (; j >= 0; j--)
{
if (currElement < arr[j])
arr[j + 1] = arr[j];
else
break;
}
arr[j + 1] = currElement;
}
static void Main(String[] args)
{
//No need to capture the size of array. We use array's length property instead.
Console.ReadLine();
var arr_temp = Console.ReadLine().Split(' ');
var arr = Array.ConvertAll(arr_temp, int.Parse);
for (var i = 1; i < arr.Length; i++)
{
Insert(arr, i);
Console.WriteLine(String.Join(" ", arr));
}
}
}
