Shell Sort

shell_sort.js

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D

// Test Case
// Input
// 5
// 5
// 1
// 4
// 3
// 2

// Output
// 2
// 4 1
// 3
// 1
// 2
// 3
// 4
// 5

var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n').map(Number);
var n = input.shift();
var m = 0;
var g = [1];
var count = 0;

function insertionSort(array, n, g) {
  for (var i = g; i < array.length; i++) {
    var v = array[i];
    var j = i - g;
    while (j >= 0 && array[j] > v) {
      var tmp = array[j + g];
      array[j + g] = array[j];
      array[j] = tmp;
      j -= g;
      count++;
    }
  }
}

function shellSort(array, n) {
  for (var i = 1; i < n; i++) {
    g[i] = g[i - 1] * 3 + 1;
  }
  g = g.filter(function(j) {
    return (j <= n);
  });
  m = g.length;
  g.reverse();

  for (var i = 0; i < m; i++) {
    insertionSort(array, n, g[i]);
  }

  console.log(m);
  console.log(g.join(' '));
  console.log(count);
  console.log(array.join('\n'));
}

shellSort(input, n);