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
2
5
1 1 1 2 2
5
2 1 3 1 2
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
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))Other Solutions
