Hackerrank Insertion Sort – Part 1 problem solution

Hackerrank Insertion Sort – Part 1 problem solution – 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.

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with a nearly sorted list.

Insert element into sorted list
Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert e into the array so that it remains sorted?

Since this is a learning exercise, it won’t be the most efficient way of performing the insertion. It will instead demonstrate the brute-force method in detail.

Hackerrank Insertion Sort – Part 1 problem solution in Python.

#!/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)

Insertion Sort – Part 1 problem solution in Java.

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(" "))
    
});