William Dickerson

Animating Figures with D3 and setTimeout()

June 27th, 2016 | by William Dickerson

Recently, I set off to make an animation of the insertion sort algorithm using D3 and some SVG elements. Here's the insertion sort algorithm in JavaScript:

function insertionSort(A) {
    for(var j=1;j<A.length;j++) {
        var key = A[j];
        var i = j - 1;
        while(i>=0 && A[i]>key) {
            A[i+1] = A[i];
            i = i - 1;
        }
        A[i+1]=key;
    }
}

And here's an SVG drawing of an array using D3:

function makeVisual(A){      
    //Clear a div and prepare an SVG area for drawing
    document.getElementById("visual-div").innerHTML="";  
    var visualArea = d3.select("#visual-div")
                   .append("svg")
                   .attr("width","100%")
                   .attr("height","100%")
                   .attr("viewBox","0 0 600 600");
    
    //Determine bar width and make a height scale
    var barWidth = 500/A.length;
    var hScale = d3.scale.linear()
          .domain([0,d3.max(A)])
          .range([ 0, 250 ]);
    
    //Append some data
    var visualBars = 
        visualArea.append("g")
                  .selectAll("bars")
                  .data(A).enter();
     
    //Draw bars 
    visualBars.append("rect")
        .attr("x", function(d,i){return 60+(i*barWidth);} ) 
        .attr("y", function(d){return 250-hScale(d);} )
        .attr("height",function(d){return hScale(d);})
        .attr("width",barWidth-10)
        .attr("class","bar");
}

Here's what makeVisual() does with the array myA = [5,2,4,6,1,3]:

We'd like to use makeVisual() within the for loop of insertionSort(). The first problem we run into is that the loop executes so quickly that you don't see the bars move, but only the final sorted array. (Actually, the DOM isn't even updated until the for loop completes.) Because there is no wait() function in JavaScript, we turn to setTimeout():

function insertionSort(A) {
    for(var j=1;j<A.length;j++) {
        var key = A[j];
        var i = j - 1;
        while(i>=0 && A[i]>key) {
            A[i+1] = A[i];
            i = i - 1;
        }
        A[i+1]=key;
        setTimeout(makeVisual,j*1000,A.splice());
    }
}

Here's everything in action: (click "result" to restart the animation.)

Some intricacies of setTimeout()

• The 3rd, 4th, 5th... arguments you pass to setTimeout() are passed as the 1st, 2nd, 3rd... arguments to the function you are delaying.

• We aren't adding any pause within the for loop; we are simply requesting some code to run in the future. Think of our setTimeout(makeVisual,j*1000,A.splice()) command as queuing up a single frame of the animation.

• Because our for loop finishes executing before our first timer runs out, we can't use setTimeout(makeVisual,j*1000,A). A will be sorted before makeVisual(A) ever runs! By using A.splice(), we create a new array with the current contents of A.

My insertion sort animation is a work in progress, but check it out here.