Insertion Sort Part 2 Hackerrank Solution in C

   September 7, 2022

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

Output for Insertion Sort Part 2 Hackerrank Solution in C
Best 100+ Python Projects with source code

Also Read:

Share:

Author: Ayush Purawr