D3 Examples - Selection Sort

Selection Sort

This animation demonstrates the selection sort.

The main problem was to chain was to chain transition. I was doing a data join at every iteration, which discarded my current transition.

Instead, i just chained transition, and acceded the current state of the array in the transition.

Array is shuffled at the end of the algorithm. Note the filter() call on the transitions. Without the filter, sort() function would be called ten times, as there is ten .rect elements.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<title>Selection sort</title>
<style>
text {
  font: bold 48px monospace;
  text-anchor: middle;
}
</style>
<body>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>
var data = [0,1,2,3,4,5,6,7,8,9];
​
var margin = {top: 200, right: 100, bottom: 200, left: 100};
​
var width = 1000-margin.left-margin.right;
var height = 900-margin.top-margin.bottom;
​
var rectHeight = 60;
var rectWidth = width/data.length;
​
d3.shuffle(data);
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 + ")");
var rects = svg.selectAll(".rect")
  .data(data)
  .enter()
  .append("g")
  .attr("transform", function(d,i){ return "translate("+d*rectWidth+",10)" })
  .attr("class","rect");
rects.append("rect")
  .attr("width",rectWidth)
  .attr("height",rectHeight)
  .attr("fill","#245")
  .attr("opacity",function(d,i) { return i/10});
rects.append("text")
  .attr("x",rectWidth/2)
  .attr("y",rectHeight/2+rectHeight/4)
  .text(function(d,i) {return i+1;});
var min,minIndex;
var lastTrans;
sort();
function sort() {
  var outer = 0;
  var inner = 0;
  for (outer=0;outer<data.length;outer++) {
    console.log(outer,data.length);
    min = data[outer];
    minIndex = outer;
    for (inner=outer+1;inner<data.length;inner++) {
      if (min>data[inner]) { min = data[inner]; minIndex = inner; }
    }
    swap(data,outer,minIndex);
    //grab update selection
    if (outer === 0) {
      lastTrans = svg.selectAll(".rect").data(data).transition().duration(1200);
      lastTrans.attr("transform", function(d,i) {
        return "translate("+ (d*rectWidth) +",10)";
      });
    } else {
      lastTrans = lastTrans.transition().attr("transform", function(d,i) {
        return "translate("+ (data[i]*rectWidth) +",10)";
      });
      if (outer == data.length-1) {
        lastTrans.each("end",function(){
           d3.shuffle(data);
           svg.selectAll(".rect").data(data).transition().duration(1200)
           .attr("transform", function(d,i) {
            return "translate("+ (d*rectWidth) +",10)";
           }).filter(function(d,i){ return i==0}).each("end",function(){sort()});
        })
      }
    }
  }
}
function restart() {
  sort();
}
function swap(array,indexA,indexB) {
  if (indexA == indexB) return;
  var temp = data[indexA];
  data[indexA]= data[indexB];
  data[indexB] = temp;
}
</script>
​
    