An implementation of shellsort with a visualization based off of Mike Bostock's Quicksort animation.
Red lines indicate every hth index as the algorithm performs insertion sort for h independent interleaved sorted subsequences.
An implementation of shellsort with a visualization based off of Mike Bostock's Quicksort animation.
Red lines indicate every hth index as the algorithm performs insertion sort for h independent interleaved sorted subsequences.
<!DOCTYPE html> | |
<meta charset="utf-8"> | |
<body> | |
<style> | |
line { | |
stroke: #000; | |
stroke-width: 5px; | |
} | |
</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 = 120, | |
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 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) + ")"); | |
var line = svg.selectAll("line") | |
.data(data) | |
.enter().append("line") | |
.attr("index", function(d, i) { return "i" + i; }) | |
.attr("x2", function(d) { return 0; }) | |
.attr("y2", function(d) { return - heightScale(d); }) | |
.attr("transform", function(d, i) { return "translate(" + x(i) + ")"; }); | |
// 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; | |
// 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 "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(200) | |
.attr("transform", function(d, i) { return "translate(" + x(i) + ")"; }) | |
.style("stroke", function(d, i) { return i % h == 0 ? "red" : null; }); | |
break; | |
} | |
} | |
}, 250); | |
</script> |
// sorts array in place and returns an array of actions | |
function shellsort(arr) { | |
var N = arr.length, | |
h = Math.floor(N/3) + 1, | |
actions = []; | |
actions.push({type: "parameter", val: h}) | |
while(h >= 1){ | |
for(var i = h; i < N; i++) { | |
for(var j = i; j >= h && arr[j] < arr[j-h]; j -= h) { | |
swap(arr, j, j-h); | |
actions.push({type: "swap", i: j, j: j-h}); | |
} | |
} | |
h = Math.floor(h/3); | |
actions.push({type: "parameter", val: h}); | |
} | |
return actions; | |
} | |
function swap(arr, i, j) { | |
var t = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = t; | |
} | |
// Node or browser? | |
if (typeof window === 'undefined') { | |
module.exports = shellsort; | |
} else { | |
window.shellsort = shellsort; | |
} |