In Insertion Sort Part 2 Hackerrank Solution in C, we are given an array, we need to sort it using insertion sort and print all the intermediate steps. Insertion sort is performed by placing all elements in their proper order one by one.

**Example**

arr = [3, 4, 7, 5, 6, 2, 1]

**Output**

3 4 7 5 6 2 1 3 4 7 5 6 2 1 3 4 5 7 6 2 1 3 4 5 6 7 2 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7

In the first step, we consider only the first element i.e 3 which will be in the sorted order. In the next step, we consider the first 2 elements. 4 is greater than its predecessor(s) so it is in the correct order. In the next step also 7 is greater than its predecessor(s) so we leave it unchanged. Now, in the next step, we have 5. 5 is greater than 3 and 4 but smaller than 7, so it is inserted before 7. Similarly, all other elements are placed in their order and we get the sorted array.

## Approach for Insertion Sort Part 2

To solve Insertion Sort Part 2, we loop from index 1 to the last index and find the position for each index. The value at that index is stored and compared with its predecessors. If the value of the predecessor is greater than the key value, it moved one place forward to make room for the key value. The value at the proper index is then swapped with the key value. We don’t loop through the 0th index as it will always be sorted as there is only one element.

## Insertion Sort Part 2 Hackerrank Solution in C

```
void insertionSort2(int n, int arr_count, int* arr) {
for(int i=1; i < n; i++){
int ele = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > ele) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = ele;
for(int k=0;k<n;k++){
printf("%d ", arr[k]);
}
printf("\n");
}
}
```

### Input

```
6
1 4 3 5 6 2
```

### Output

```
1 4 3 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 3 4 5 6 2
1 2 3 4 5 6
```

### HackerRank Snapshot

**Also Read:**

- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
- HackerRank Day 12 Solution in Python: Inheritance