(D3.js) How to update every single step of the graph in animation?-CodePudding

First of all, I want to animate the steps of Quick Sort, to learn its behavior.

The Quick Sort algorithm is fine (of course) from a reference book.

But I can only view only the start and end of the Quick Sort movement. Let me know how to view every single step in Quick Sort by d3.js. (I'm a JS beginner.)

My temporary codes are as below. Thnx in advance.

index.html:

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta http-equiv="Content-Type" content="text/html"; charset="utf-8" />
        <title>Sort Viz 03</title>
        <script src="https://d3js.org/d3.v7.min.js"></script>
        <script src="draw_functions.js"></script>
        <script src="quickSort.js"></script>
        <style>
            body {
                font-family: "Helvetica Neue", Helvetica, sans-serif;
                font-size: 30px;
                color: #333;
            }
            /* rect {
                fill: orange;
            } */
            #counter{
                width: 100px;
                height:100px;
                color: black;
                font: 500 60px system-ui;
            }
            div {
                font: 1000 30px system-ui;
            }
        </style>
    </head>

    <body>

        <h1 id="title0">Quick Sort</h1>
        <div id="counter0">0</div>
        <div id="chart0"></div>

        <script>
            var myData = d3.range(10);
            d3.shuffle(myData);
            initDraw(myData, "chart", 0);
            quickSort(myData, 0, myData.length, "chart", 0);
        </script>

    </body>
</html>

quickSort.js:

function quickSort(items, left, right, id, num) {

    if (right - left <= 1) return;

    var pivot_index = Math.floor((left   right) / 2);
    var pivot = items[pivot_index];

    swap(items, pivot_index, right - 1);
    redraw(items, id, num);

    var i = left;
    for (j = left; j < right - 1;   j) {
        if (items[j] < pivot) {
            swap(items, i  , j);
            redraw(items, id, num);
        }
    } 
    swap(items, i, right - 1);
    redraw(items, id, num);

    quickSort(items, left, i, id, num);
    quickSort(items, i   1, right, id, num);

    redraw(items, id, num);

    // console.log("#####", items ,"#####", left, right, num);
}


function swap(items, i, j) {

    // console.log("@@@@@", items, i, j, (i == j), "@@@@@")

    var tmp = items[i];
    items[i] = items[j];
    items[j] = tmp;

    console.log("@@@@@", items, i, j, (i == j), "@@@@@")

}

draw_functions.js:

const graphImageSizeX = 300;
const graphImageSizeY = 200;
const margin = {top: 20, right: 20, bottom: 20, left: 20};
const width = graphImageSizeX - margin.left - margin.right;
const height = graphImageSizeY - margin.top - margin.bottom;


var durationTime = 1000;



function initDraw(data, id, num) {


    console.log("#####", data ,"#####", id, num);


    var bandScale = d3.scaleBand()
    .domain(d3.range(data.length))
    .range([margin.left, width - margin.right])
    .paddingInner(0.05);

    d3.select("#"   id   num).append("svg")
    .attr("width", width)
    .attr("height", height)
    .append("g")
    .attr("transform", "translate("   0   ","   0   ")");
  
    d3.select("#"   id   num).select("svg").select("g")
    .selectAll('rect')
    .data(d3.range(data.length))
    .join('rect')
    .attr("id", function(d, i) { return( "rect"   num   "_"   i ); })
    .attr('fill', "orange")
    .attr('width', bandScale.bandwidth())
    .attr('height', function(d, i) { return Math.floor(data[i] / data.length * height); })
    .attr('x', function(d) { return bandScale(d); })
    .attr("y", function(d, i) { return height - Math.floor(data[i] / data.length * height); })
}       


async function redraw(data, id, num) {


    console.log("#####", data ,"#####", id, num);


    var bandScale = d3.scaleBand()
    .domain(d3.range(data.length))
    .range([margin.left, width - margin.right])
    .paddingInner(0.05);

    d3.select("#"   id   num).select("svg").select("g")
    .selectAll('rect')
    // .data(data)
    // .enter()
    .transition()
    .duration(durationTime)
    .attr('fill', "brown")
    .attr('width', bandScale.bandwidth())
    .attr('height', function(d, i) { return Math.floor(data[i] / data.length * height); })
    .attr('x', function(d) { return bandScale(d); })
    .attr("y", function(d, i) { return height - Math.floor(data[i] / data.length * height); })
}

CodePudding user response：

The problem is that you're calling redraw() without waiting for the transition to complete (it takes 1s i.e. durationTime, while the subsequent redraw calls must be taking a few milliseconds).

The solution is to save all the steps in an array. And then later re-use it to redraw with a time interval between each redraw() call. Use setInterval for that.

I have created a working codepen with the mentioned changes.

replace all calls to redraw() with a steps.push (ref: Array push method)
After the sorting is complete. Call redraw steps.length times with a time interval of something greater than durationTime (ref: setInterval)
Once you've finished redrawing, clearInterval to cleanup the setInterval (ref: clearInterval)

CodePudding user response：

I have to be honest to tell you the truth. This is what I have already done.

[Comparing some sorting methods.][1] [1]: https://youtu.be/QYBVpZpiBfg

This sample is using "recording" step-by-step in sorting. But, as you can see, I made failure for merge sort.

So, I want to look for the another method, not using "recording & replaying", but simply "hooking" the sorting process -- if possible --.

Otherwise, some sorting methods will be harder to (re)play its animation, that is not described by the "swap" analogy. (recorded data will be complex.)

Sorry for not enough to be honest. But what should I do in this situation?

Thanks in advance.