In this Hackerrank Insertion Sort - Part 1 problem we have given a sorted list and an unsorted number in the right cell or list, we need to insert the integer number inside the list and it needs to be remains sorted.

Hackerrank Insertion Sort - Part 1 problem solution


Foundation course by prepbytes

Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'insertionSort1' function below.
#
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER_ARRAY arr
#

def insertionSort1(n, arr):
    target = arr[-1]
    idx = n-2

    while (target < arr[idx]) and (idx >= 0):
        arr[idx+1] = arr[idx]
        print(*arr)
        idx -= 1

    arr[idx+1] = target
    print(*arr)

if __name__ == '__main__':
    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    insertionSort1(n, arr)


Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {
    public static int[] getStdinArray() {
        int[] list;
        Scanner scanner = new Scanner(System.in);
        
        list = new int[scanner.nextInt()];
        
        for (int i = 0; (scanner.hasNextInt() && (i < list.length)); i++)
            list[i] = scanner.nextInt();
        
        return list;
    }
    
    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i);
            System.out.print(" ");
        }
        
        System.out.println("");
    }
    
    public static void main(String[] args) {
        int[] array = getStdinArray();
        int temp;
        
        for (int i = array.length - 1; i > 0; i--) {
            temp = array[i];

            if (array[i - 1] > temp) {
                array[i] = array[i - 1];
                printArray(array);
                
                array[i - 1] = temp;
            }
        }
        
        printArray(array);
    }
}


Problem solution in C++ programming.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

/* Head ends here */

void insertionSort(vector <int>  ar) {

    int to_be_sorted = *( ar.end() - 1);
    int i ;
    for (i = ar.size(); i > 1; --i) {
        if(to_be_sorted < ar[i-2]) {
            ar[i-1] = ar[i-2];
            for (int j = 0; j < ar.size(); ++j) {
                cout << ar[j] << " ";
            }
            cout << endl;
        }
        else {
            break;
        }
    }
        ar[i-1] = to_be_sorted;
            for (int j = 0; j < ar.size(); ++j) {
                cout << ar[j] << " ";
            }
            cout << endl;
}


/* Tail starts here */
int main() {
   vector <int>  _ar;
   int _ar_size;
cin >> _ar_size;
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
   int _ar_tmp;
   cin >> _ar_tmp;
   _ar.push_back(_ar_tmp); 
}

insertionSort(_ar);
   
   return 0;
}


Problem solution in C programming.

#include <stdio.h>

void print(int ar_size, int* ar) {
    int i;
    for(i=0; i<ar_size; i++) {
        printf("%d ", ar[i]);
    }
    printf("\n");
}

#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */
void insertionSort(int ar_size, int *  ar) {
    int j = ar_size-1;
    int v = ar[j];
    while(v < ar[j-1]) {
        ar[j] = ar[j-1];
        j--;
        print(ar_size, ar);
    }
    ar[j] = v;
    print(ar_size, ar);
}

/* Tail starts here */
int main() {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size, _ar);
   
   return 0;
}


Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding("ascii");
process.stdin.on("data", function (input) {
    var arr = input.split(/\n/)[1].split(/ /)
    for (var ii = 0; ii < arr.length; ii++)
        arr[ii] = +arr[ii]
        
    var len = arr.length,
        c = len - 2,
        v = arr[len - 1]
    
    while (arr[c] > v && c >= 0) {
        arr[c + 1] = arr[c]
        c--
        console.log(arr.join(" "))
    }
    arr[c + 1] = v
    console.log(arr.join(" "))
    
});