HackerRank Running Time of Algorithms problem solution

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.

Running Time of Algorithms
The running time of an algorithm for a specific input depends on the number of operations executed. The greater the number of operations, the longer the running time of an algorithm. We usually want to know how many operations an algorithm will execute in proportion to the size of its input, which we will call N.

What is the ratio of the running time of Insertion Sort to the size of the input? To answer this question, we need to examine the algorithm.

Function Description

Complete the runningTime function in the editor below.

runningTime has the following parameter(s):

• int arr[n]: an array of integers

Returns

• int: the number of shifts it will take to sort the array

HackerRank Running Time of Algorithms problem solution in Python.

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

Running Time of Algorithms problem solution in Java.

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++.

#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.

#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.

'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); });