HackerRank Running Time of Algorithms problem solution

In this HackerRank Running Time of Algorithm problem, Can you modify Insertion Sort implementation to keep track of the number of shifts it makes while sorting? The only thing you should print is the number of shifts made by the algorithm to completely sort the array. A shift occurs when an element’s position changes in the array. Do not shift an element if it is not necessary.

Problem solution in Python programming.

#!/usr/bin/env python

import sys


def insertion_sort(ar):
    if len(ar) <= 1:
        print(0)
        return(ar)
    else:
        shifts = 0
        
        for j in range(1, len(ar)):
            for i in reversed(range(j)):
                if ar[i + 1] < ar[i]:
                    ar[i], ar[i + 1] = ar[i + 1], ar[i]
                    shifts += 1
                else:
                    break
        
        print(shifts)
        return(ar)
                
if __name__ == '__main__':
    s = int(sys.stdin.readline())
    ar = list(map(int, sys.stdin.readline().split()))
    insertion_sort(ar)

Problem solution in Java Programming.

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in=new Scanner(System.in);
        int N=Integer.parseInt(in.nextLine());
        String[] tokens=in.nextLine().split("[ ]+");
        int[] A=new int[N];
        for(int i=0;i<N;++i)
            A[i]=Integer.parseInt(tokens[i]);
        int ans=0;
        for(int i=1;i<N;++i){
            int val=A[i];
            int j=i-1;
            for(;j>=0 && A[j]>val;--j){
                A[j+1]=A[j];
                ans++;
            }
            A[j+1]=val;
        }
        System.out.println(ans);
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int num;
    vector<int> input;
    cin >> num;
    for (int i = 0; i < num; ++i) {
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    int count = 0;
    for (int i = 1; i < num; ++i) {        
        int val = input[i];
        for (int j = i - 1; j >= 0; --j) {
            if (input[j] > val) {
                input[j + 1] = input[j];
                input[j] = val;
                ++count;
            } else {
                break;
            }
        }
    }
    cout << count << endl;
    
    return 0;
}

Problem solution in C programming.

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

int placeElement(int ar_size, int *  ar) {

    int temp = ar[ar_size-1];
    int shift = 0;
    for(int i=ar_size - 1; i>=0;i--)
    {
        if(ar[i-1] > temp)
        {
            ar[i] = ar[i-1]; 
            shift++;
        } else {
            ar[i]= temp;
            break;
        }
        
    }
   return shift;
    
}


/* Head ends here */
void insertionSort(int ar_size, int *  ar) {

    int shifts=0;
    for(int i = 2; i <= ar_size; i++) {
        shifts += placeElement(i,ar);
        
    }
    printf("%dn", shifts);
}

/* 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.

'use strict';


function binarySearch(arr, n, idx0, idx1) {
    if (n < arr[idx0]) { return idx0; }
    if (arr[idx1] <= n)  { return idx1 + 1; }

    // arr[idx0] <= n < arr[idx1]
    if (idx1 - idx0 <= 1) { return idx0 + 1; }
    var idx = idx0 + Math.floor((idx1 - idx0 + 1) / 2);
    if (n < arr[idx]) { return binarySearch(arr, n, idx0, idx); }
    if (arr[idx] <= n)  { return binarySearch(arr, n, idx, idx1); }

    return idx;
}


function processData(input) {
    var parse_fun = function (s) { return parseInt(s, 10); };
    var lines = input.split('n');
    var N = parse_fun(lines.shift());
    var a = lines.shift().split(' ').splice(0, N).map(parse_fun);

    var res = 0;
    var b = [a[0]];

    for (var i = 1; i < a.length; i++) {
        var idx = binarySearch(b, a[i], 0, b.length - 1);
        res += (i - idx);
        b.splice(idx, 0, a[i]);
    }

    console.log(res);
}


process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) { _input += input; });
process.stdin.on("end", function () { processData(_input); });