Shellsort II

An improvement upon a previous presentation of Shellsort. Here, each color indicates the elements which may be swapped during a given iteration of Shellsort.

The number of colors converges to 1 by following a sequence generated by the following code:

  while (h < N/3) h = 3*h + 1;

  ...
  
  //in the main loop
  
  h = h/3

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<style>

line {
  stroke: #000;
  stroke-width: 5;
}

</style>
<script src="shellsort.js"></script>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

// Modified from Mike Bostock's https://gist.github.com/mbostock/1582075

var margin = {top: 230, right: 30, bottom: 230, left: 30},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom;

var n = 100,
    index = d3.range(n),
    data = shuffle(index.slice());

var x = d3.scale.ordinal().domain(index).rangePoints([0, width]),
    heightScale = d3.scale.linear().domain([0, n - 1]).range([10, 200]);
    a = d3.scale.linear().domain([0, n - 1]).range([-Math.PI / 4, Math.PI / 4]);

var color = d3.scale.category20();

var svg = d3.select("body").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + (margin.top + height) + ")");

// Fisher–Yates shuffle
function shuffle(array) {
  var i = array.length, j, t;
  while (--i > 0) {
    j = ~~(Math.random() * (i + 1));
    t = array[j];
    array[j] = array[i];
    array[i] = t;
  }
  return array;
}

var actions = shellsort(data).reverse();

var h = 1,
    current = 0;

// highlight every hth item, where h is the current value of h in shellsort
setInterval(function step() {
  var action = actions.pop();
  if (action) switch (action.type) {
    case "index": {
      current = action.val;
      step();
      break;
    }
    case "parameter": {
      h = action.val;
      step();
      break;
    }
    case "swap": {
      var t = line[0][action.i];
      line[0][action.i] = line[0][action.j];
      line[0][action.j] = t;
      line.transition().duration(350)
        .attr("transform", function(d, i) { return "translate(" + x(i) + ")"; })
        .style("stroke-width", function(d, i) { return i === current ? 10 : 5})
        .style("stroke", function(d, i) { return color(i % h)});
      break;
    }
  }
}, 400);

</script>

https://d3js.org/d3.v3.min.js