Skip to content

Instantly share code, notes, and snippets.

@yamadayuki
Created December 8, 2016 20:20
Show Gist options
  • Save yamadayuki/ec562314fccff58f11396bc5e2f53d36 to your computer and use it in GitHub Desktop.
Save yamadayuki/ec562314fccff58f11396bc5e2f53d36 to your computer and use it in GitHub Desktop.
Shell Sort
// 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment