HackerRank Insertion Sort Advanced Analysis

In this post, we will solve HackerRank Insertion Sort Advanced Analysis Problem Solution.

Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of shifts an insertion sort performs when sorting an array?
If k[i] is the number of elements over which the ¿th element of the array has to shift, then the total number of shifts will be k[1] + k[2]+ … + k[n].
Example
arr = [4, 3, 2, 1]

Array		Shifts
[4,3,2,1]	
[3,4,2,1]	1
[2,3,4,1]	2
[1,2,3,4]	3

Total shifts = 1 + 2 + 3 = 6

Function description

Complete the insertionSort function in the editor below.

insertionSort has the following parameter(s):

int arr[n]: an array of integers

Returns
– int: the number of shifts required to sort the array

Input Format
The first line contains a single integer t, the number of queries to perform.
The following t pairs of lines are as follows:

The first line contains an integer n, the length of arr.
The second line contains n space-separated integers arr[i].

Sample Input

Sample Output

0  
4

Explanation

The first query is already sorted, so there is no need to shift any elements. In the second case, it will proceed in the following way.

Array: 2 1 3 1 2 -> 1 2 3 1 2 -> 1 1 2 3 2 -> 1 1 2 2 3
Moves:   -        1       -    2         -  1            = 4

HackerRank Insertion Sort Advanced Analysis Problem Solution

Insertion Sort Advanced Analysis C Solution

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
/* Enter your code here. Read input from STDIN. Print output to STDOUT */

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

typedef struct _bt{
    int val;
    int lcounter;
    int rcounter;
    struct _bt * left;
    struct _bt * right;
} binary_tree;


binary_tree * new_binary_tree(int val) {
        binary_tree * b = (binary_tree*) malloc(sizeof(binary_tree));
        b->lcounter = 0;
        b->rcounter = 0;
        b->left = NULL;
        b->right = NULL;
        b->val = val;
    return b;
}

void insert(binary_tree * b, int val) {
 
    if (val <= b->val) {
        if (b->left) 
            insert(b->left, val);
        else 
            b->left = new_binary_tree(val); 
        b->lcounter++;
    } else {
        if (b->right) 
            insert(b->right, val);
        else 
            b->right = new_binary_tree(val); 
        b->rcounter++;
    }
}

int getnnodes(binary_tree * b) {
    if(!b) return 0;
    return 1 + b->lcounter + b->rcounter;
}

binary_tree * balance_aux(binary_tree *a) {
    if (!a) return a;
    if (abs(a->lcounter - a->rcounter) <= 1) return a;
    
    if (a->lcounter > a->rcounter) {
        binary_tree *b = a->left;  /* has to exist */
        binary_tree *c = b->right; /* has to exist */
        binary_tree *d = b->left;  /* may not exist */
        binary_tree *e = b->right; /* may not exist */
        
        a->left = e;
        a->lcounter = getnnodes(e);
        b->right = a;
        b->rcounter = getnnodes(a);
        b->lcounter = getnnodes(d);
                
        return b;
    }
    else {
        binary_tree *b = a->right;  /* has to exist */
        binary_tree *c = b->left; /* has to exist */
        binary_tree *d = b->right;  /* may not exist */
        binary_tree *e = b->left; /* may not exist */
        
        a->right = e;
        a->rcounter = getnnodes(e);
        b->left = a;
        b->lcounter = getnnodes(a);
        b->rcounter = getnnodes(d);
                
        return b;      
    }
       
}

binary_tree * balance(binary_tree *a) {
        a = balance_aux(a);
        if (a->left) a->left = balance(a->left);
        if (a->right) a->right = balance(a->right);
    return a;
}

int getnbigger(binary_tree * b, int val) {
    if (!b) return 0;
 
    if (val < b->val) {
        return (b->rcounter + 1 + getnbigger(b->left, val));
    }
    
    return getnbigger(b->right, val);
}

void clean(binary_tree * b) {
    if (b) {
        clean(b->left);
        clean(b->right);
        free(b);
    }
}

int main(void) {
    
 
    int T, N;
    long long int nswaps;    
    
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        int i, data;
        scanf("%d", &data);        
        binary_tree * tree = new_binary_tree(data);
        nswaps = 0;
        for(i=1; i<N;i++) {
            scanf("%d", &data);
            insert(tree, data);
            if (i%200 == 0)
                tree = balance(tree);
            nswaps += getnbigger(tree, data);
        }
                        
        printf("%lld\n", nswaps);
        clean(tree);
    }
    
    return 0;
}

Insertion Sort Advanced Analysis C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long int ll;
ll merge(vector<int> &arr, int m, int l, int r){
    ll inv_cnt=0;
    int llen=m-l+1, rlen=r-m;
    vector<int> larr(llen), rarr(rlen);
    for(int i=0; i<llen; i++) larr[i]=arr[l+i];
    for(int i=0; i<rlen; i++) rarr[i]=arr[m+1+i];
    int i=0, j=0;
    while(i<llen && j<rlen){
        if(larr[i]<=rarr[j]){
            arr[l]=larr[i];
            l++;
            i++;
        }
        else{
            arr[l]=rarr[j];
            j++;
            l++;
            inv_cnt+=llen-i;
        }
    }
    while(i<llen){
        arr[l]=larr[i];
        l++;
        i++;
    }
    while(j<rlen){
        arr[l]=rarr[j];
        j++;
        l++;
    }
    return inv_cnt;
}

ll mergeSort(vector<int> &arr, int l, int r){
    if(l>=r) return 0;
    int m=(l+r)/2;
    ll v1=mergeSort(arr,l,m);
    ll v2=mergeSort(arr,m+1,r);
    return v1+v2+merge(arr,m,l,r);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        vector<int> arr(n);
        for(int i=0; i<n; i++) scanf("%d",&arr[i]);
        printf("%lld\n",mergeSort(arr,0,n-1));
    }
    return 0;
}

Insertion Sort Advanced Analysis C Sharp Solution

using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Collections.Generic;

//https://www.hackerrank.com/challenges/insertion-sort
namespace Sort_Insertion_Sort_Advanced_Analysis
{
    class Program
    {
        static void Main(string[] args)
        {
            
                int T = int.Parse(Console.ReadLine());

                for (int i = 0; i < T; i++)
                {
                    int N = int.Parse(Console.ReadLine());
                    String[] stringValues = Console.ReadLine().Split(' ');
                    int[] intValues = Array.ConvertAll(stringValues, int.Parse);

                    CountStepsMergeSort(intValues);
                    Console.WriteLine(count);
                    count = 0; 
                }
                Console.ReadKey();
      
        }


        private static long count = 0;

        private static void CountStepsMergeSort(int[] intValues)
        {
            int length = intValues.Length;
            
            MergeSort(intValues, 0, length - 1);
        }

        private static void MergeSort(int[] intValues, int p1, int p2)
        {
            if (p1 >= p2) return;
            int mid = p1 + ((p2 - p1) >> 1);
            
            MergeSort(intValues, p1, mid);
            MergeSort(intValues, mid + 1, p2);
            Merge(intValues, p1, mid, p2);
        }

        private static void Merge(int[] intValues, int p1, int mid, int p2)
        {
            int i = p1, j = mid +1;
            Queue<int> queue = new Queue<int>();
            while (i <= mid && j <= p2)
            {
                if (intValues[i] <= intValues[j])
                {
                    queue.Enqueue(intValues[i++]);
                }
                else
                {
                    queue.Enqueue(intValues[j++]);
                    count += mid - i + 1;
                }
            }
            while (j <= p2)
            {
                queue.Enqueue(intValues[j++]);
            }
            while (i <= mid)
            {
                queue.Enqueue(intValues[i++]);
            }
            for (int k = p1; k <= p2; k++)
            {
                intValues[k] = queue.Dequeue();
            }
        }

    }       
}

Insertion Sort Advanced Analysis Java Solution

import java.util.*;

public class Main {

    static int[] arr = new int[10000001];

    public static int assign (int a, int[] arr, int i) {
        int j = read(arr, a);
        while (a <= 10000000) {
            arr[a]++;
            a += a&(-a);
        }
        return i - j;
    }

    public static int read (int[] arr, int a) {
        int x = 0;
        while (a > 0) {
            x = x + arr[a];
            a -= a&(-a);
        }
        return x;
    }

    public static void main(String[] args) {

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

        while (numOfQueries > 0) {
            int arrayLength = in.nextInt();
            Arrays.fill(arr, 0);
            long ans = 0;

            for (int i = 0; i < arrayLength; i++) {
                ans = ans + assign(in.nextInt(), arr, i);
            }
            System.out.println(ans);
            numOfQueries--;
        }
    }
}

Insertion Sort Advanced Analysis JavaScript Solution

function merge(array, temp, left, mid, right){
    var i = left, 
        j = mid, 
        k = left,
        inversions = 0
    
    while (i <= mid - 1 && j <= right){
        if (array[i] <= array[j]) {
            temp[k] = array[i];
            i++;
        } else {
            temp[k] = array[j];
            j++;
            inversions += (mid - i);
        }    
        k++;
    }
    while (i <= mid - 1){
        temp[k] = array[i];
        k++;
        i++
    }
    while (j <= right) {
        temp[k] = array[j];
        k++;
        j++;
    }
    for(var idx = left; idx < right+1; idx++) {
        array[idx] = temp[idx];
    }
    return inversions;
}

function merge_and_count(array, temp, lower, upper) {
        var invs = 0;
        if (lower < upper) {
            var mid = Math.floor((upper + lower)/2);
            invs = merge_and_count(array, temp, lower, mid);
            invs += merge_and_count(array, temp, mid + 1, upper);
            invs += merge(array, temp, lower, mid + 1, upper);
        }    
        return invs;
}

function processData(input) {
    //Enter your code here
    var inputS = input.split("\n");
    var testCases = parseInt(inputS[0]);
    var j = 0;
    for(var i = 1; i <= testCases; i++) {
        var n = parseInt(inputS[j+1]);
        //console.log(n);
        var numbers = inputS[j+2].split(" ");
        numbers = numbers.map(Number);
        //console.log(numbers);
        j = j + 2;
        var k = 0;
        var temp = Array(n);
        k = merge_and_count(numbers, temp, 0, n-1);
        
        /*
        for(var a = 1; a < n; a++)
        {
            var key = numbers[a];
            var b = a-1;
            
            while(b >= 0 && numbers[b] > key)
            {     
                k++;
                numbers[b+1] = numbers[b];
                b = b - 1;
                numbers[b+1] = key;
            }
        }
        */
        
        /*
        for(var a = 0; a < numbers.length; a++) {
            var m = a;

            var low = numbers[m-1];
            var high = numbers[m];

            while(high < low) {
                k++;

                numbers[m] = low;
                numbers[m-1] = high;

                m--;
                low = numbers[m-1];
                high = numbers[m];
            }
            
        } */
        console.log(k);
    }
} 

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

process.stdin.on("end", function () {
   processData(_input);
});

Insertion Sort Advanced Analysis Python Solution

class BIT:
  def __init__(self, n):
    sz = 1
    while n >= sz:
      sz *= 2
    self.size = sz
    self.data = [0] * sz
    
  def add(self, index, v):
    while index < self.size:
      self.data[index] += v
      index += index & -index
      
  def sum(self, index):
    s = 0
    while index > 0:
      s += self.data[index]
      index -= index & -index
    return s

def calc(n, arr):
  bit = BIT(max(arr))
  result = 0
  for i, v in enumerate(arr):
    result += i - bit.sum(v)
    bit.add(v, 1)
  return result

T = int(input().strip())
for t in range(T):
  n = int(input().strip())
  arr = [int(i) for i in input().strip().split()]
  print(calc(n, arr))