-
Notifications
You must be signed in to change notification settings - Fork 693
/
Solution.cs
58 lines (51 loc) · 2.02 KB
/
Solution.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
Problem: https://www.hackerrank.com/challenges/insertionsort1/problem
C# Language Version: 7.0
.Net Framework Version: 4.7
Tool Version : Visual Studio Community 2017
Thoughts :
1. Let the array containing all the sorted elements and one new element e at the end of the array be arr.
2. let the total number of elements in the array be n.
3. Initialize a value i = n-1.
4. Initialize a counter j = i-1.
5. Start a loop
5.1 if e < arr[j] then set arr[j + 1] = arr[j] and print the entire array elements separated by space character.
5.2 if e >= arr[j] then break the loop.
5.3 Decrement j by 1.
5.4 Break the loop if j < 0.
5.3 Keep repeating steps from 5.1 through 5.4 untill loop breaking condition isn't met.
6. j+1 is the correct position where e needs to be inserted. Replace (j+1)th element of array with e.
7. Print the entire array elements separated by space character one last time.
Time Complexity: O(n) //There is only one loop.
Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input.
*/
using System;
class Solution
{
static void InsertionSort(int[] arr)
{
var i = arr.Length - 1;
var currElement = arr[i];
var j = i - 1;
for (; j >= 0; j--)
{
if (currElement < arr[j])
{
arr[j + 1] = arr[j];
Console.WriteLine(String.Join(" ", arr));
}
else
break;
}
arr[j + 1] = currElement;
Console.WriteLine(String.Join(" ", arr));
}
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);
InsertionSort(arr);
}
}