Insertion Sort Advanced Analysis – HackerRank Solution

In this post, we will solve Insertion Sort Advanced Analysis HackerRank Solution. This problem (Insertion Sort Advanced Analysis) is a part of HackerRank Problem Solving series.

Solution – Insertion Sort Advanced Analysis – HackerRank Solution

C++

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

long long iNum = 0;

void cntInv(vector<int>& a, vector<int>& b, int l, int r){
    if(r - l < 2)
        return;
    int mid = (l + r) / 2;
    cntInv(b, a, l, mid);
    cntInv(b, a, mid, r);
    int i = mid - 1;
    int j = r - 1;
    int k = r - 1;
    while(i >= l && j >= mid){
        if(a[j] >= a[i])
            b[k--] = a[j--];
        else{
            iNum += j - mid + 1;
            b[k--] = a[i--];
        }
    }
    while(i >= l){
        b[k--] = a[i--];
    }
    while(j >= mid){
        b[k--] = a[j--];
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T;
    cin >> T;
    while(T--){
        vector<int> a;
        int n;
        cin >> n;
        for(int i = 0; i < n; ++i){
            int num;
            cin >> num;
            a.push_back(num);
        }
        vector<int> b(a);
        iNum = 0;
        cntInv(a, b, 0, a.size());

        cout << iNum << endl;
    }
    return 0;
}

Python

from array import array
from bisect import bisect_right

t = int(input())
for _ in range(t):
    n = int(input())
    arr = array('I', [int(i) for i in input().split()])
    sarr = array('I', [arr[0]])
    result = 0
    for i in range(1, n):
        e = arr[i]
        j = bisect_right(sarr, e)       
        sarr.insert(j, e)
        result += i - j
    print(result)  

Java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int t = in.nextInt();

        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            int[] ar = new int[n];
            for (int j = 0; j < n; j++) {
                ar[j] = in.nextInt();
                //System.err.println(ar[j]);
            }
            long c = insertSort(ar);
            System.out.println(c);
        }
    }

    static long count = 0;

    public static void mergesort(int[] arr, int p, int r) {
        int q = (p + r) / 2;
        if (p < r) {
            mergesort(arr, p, q);
            mergesort(arr, q + 1, r);
            merge(arr, p, q, r);
        }
    }

    public static void merge(int[] arr, int p, int q, int r) {
        int[] left = new int[q - p + 1];
        int[] right = new int[r - q];
        for (int i = 0; i < left.length; i++) {
            left[i] = arr[p + i];
        }
        for (int i = 0; i < right.length; i++) {
            right[i] = arr[q + i + 1];
        }

        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (i < left.length && j < right.length) {
                if (left[i] <= right[j]) {
                    arr[k] = left[i];
                    i++;
                } else {
                    arr[k] = right[j];
                    count += left.length - i;
                    j++;
                }
            } else {
                if (i < left.length) {
                    arr[k] = left[i];
                    i++;
                } else if (j < right.length) {
                    arr[k] = right[j];
                    j++;
                }
            }
        }
    }

    public static long insertSort(int[] ar) {
        count = 0;
        mergesort(ar, 0, ar.length - 1);
        return count;

    }
}

Note: This problem (Insertion Sort Advanced Analysis) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.