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:**

- Item Price Generator Hackerrank Solution
- Insertion Sort Part 2 Hackerrank Solution in C
- Extra Long Factorials Hackerrank Solution
- Java Datatypes Hackerrank Solution
- Smart Number Hackerrank Solution
- Python Average Function Hackerrank Solution
- Company Logo Hackerrank Solution
- Matrix Summation Hackerrank Solution
- A company is repainting its office – HackerRank Solution
- Maximum Product Subarray in O(N) Time – Leetcode Solution
- Minimum number of transformation steps required to make all elements of an array equal
- NxNxN Matrix in Python 3
- Boruvka’s Algorithm in Python
- Roti Prata SPOJ Problem Solution – Complete Solution Approach with C++ and Java Code
- Lee Algorithm in Python | Solution to Maze Routing Problem in Python
- Vending Machine with Python Code
- Top 20 Array Coding Questions for Online Assessment
- Heap Sort Algorithm in Python
- Heap Sort Algorithm|Heap Data Structure
- Insertion Sort Algorithm in Data Structures using Python
- Quick Sort algorithm in data structures and algorithms using Python
- Selection Sort Algorithm In Data Structures and Algorithms using Python
- Searching Algorithms: Linear Search Algorithm
- Bubble Sort Algorithm In Data Structures & Algorithms using Python
- Merge Sort Algorithm in Python
- Binary Search in python
- Linear Search Python
- Sorting Algorithms and Searching Algorithms in Python
- Binary Search In Python
- Adding three matrices