Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First, merge sort solution in Clear category for [old] Count Inversion by rainyPaddle
"use strict";
function merge(sequence, left, right){
var j = 0, i = 0, inv =0;
//merge sort
while (i < left.length || j < right.length) {
if (i == left.length) {
sequence[i+j] = right[j];
j++;
} else if (j == right.length) {
sequence[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
sequence[i+j] = left[i];
i++;
} else {
sequence[i+j] = right[j];
inv += left.length-i;
j++;
}
}
return inv;
}
function countInversion(sequence){
if(sequence.length < 2){
return 0;
}
var k = sequence.length;
var m = (k+1)/2, left = [],right = [];
left = sequence.slice(0,m);
right= sequence.slice(m,k);
//console.log(left+" -- "+right);
return countInversion(left) + countInversion(right) + merge(sequence, left, right);
}
var assert = require('assert');
if (!global.is_checking) {
assert.equal(countInversion([1, 2, 5, 3, 4, 7, 6]), 3, "Example");
assert.equal(countInversion([0, 1, 2, 3]), 0, "Sorted");
assert.equal(countInversion([99, -99]), 1, "Two numbers");
assert.equal(countInversion([5, 3, 2, 1, 0]), 10, "Reversed");
console.log("Coding complete? Click 'Check' to review your tests and earn cool rewards!");
}
Nov. 8, 2016
Comments: