Using Canvas to Animate a Sorting Algorithm in Js

Using Canvas to animate a sorting algorithm in JS

One solution is the ES6 Generator function* along with its yield statement.

That allows you to pause a function and restart it later where it has been paused:

N = 100; // Array Size
XYs = 5; // Element Visual Size
Xp = 1; // Start Pos X
Yp = 1; // Start Pos Y
var canvas;
var l = Array.apply(null, {
  length: N
}).map(Number.call, Number);

Array.prototype.shuffle = function() {
  var i = this.length,
    j, temp;
  if (i == 0) return this;
  while (--i) {
    j = Math.floor(Math.random() * (i + 1));
    temp = this[i];
    this[i] = this[j];
    this[j] = temp;
  }
  return this;
}

function map_range(x, in_min, in_max, out_min, out_max) {
  return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
}

function rainbow(x) {
  var m = map_range(x, 0, N, 0, 359);
  return 'hsl(' + m + ',100%,50%)';
}

function init() {
  canvas = document.getElementById('canvas');
  l.shuffle();
  var sort = bubbleSort(l);
  // an anim function triggered every 60th of a second
  function anim(){
    requestAnimationFrame(anim);
    draw();
    sort.next(); // call next iteration of the bubbleSort function
  }
  anim();
}

function draw() {
  if (canvas.getContext) {
    var ctx = canvas.getContext('2d');
    for (var i = 0; i < l.length; i++) {
      ctx.fillStyle = rainbow(l[i]);
      ctx.fillRect((Xp * i) * XYs, Yp * XYs, XYs, XYs);
    }
  }
}

function* bubbleSort(a) { // * is magic
  var swapped;
  do {
    swapped = false;
    for (var i = 0; i < a.length - 1; i++) {
      if (a[i] > a[i + 1]) {
        var temp = a[i];
        a[i] = a[i + 1];
        a[i + 1] = temp;
        swapped = true;
        yield swapped; // pause here
      }
    }
  } while (swapped);
}
init();

<canvas id="canvas" width="500" height="20">

I am trying to use canvas to visualize sort algorithm in javascript?

You can use async await for that: that way you don't have to touch (much) your existing code. Just make the bubble_Sort function asynchronous with the keyword async, and add an await delay() in the loop. The delay function should then be a function that returns a promise that resolves within a short delay.

As a side note, you can speed up your bubble sort a bit. The inner loop should not revisit the part of the array that is already sorted. Each time the outer loop makes a cycle, a value arrives at its final spot at the righter end of the array, so the inner loop can stop before reaching that position.

You can also save a bit on the drawing: only call draw when you perform a swap, as there is no use in drawing the same situation twice.

Here is your code with those adaptations:

// Utility function:
let delay = ms => new Promise(resolve => setTimeout(resolve, ms));
// Make the main function async
async function bubble_Sort(arr){
    // Move the initial call of draw here
    draw(array);
    await delay(5); // <---- asynchronous delay of a few milliseconds
    let size = arr.length;
    for(let i = 0; i < size; i++){
        for(let j = 0; j < size - 1 - i; j++){ // optimised algo a bit! 
            if (arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                // Only draw when something changed
                draw(array);
                await delay(5); // <---- asynchronous delay of a few milliseconds
            }
        }
    }
    return arr;
}

function draw(array) { // Just simplified it for this demo. Nothing essential.
    context.clearRect(0, 0, canvas.width, canvas.height);
    for(let i = 0; i < array.length; i++){
        context.fillRect(10 + 7*i,canvas.height-20,5,-array[i]);
    }
}

var CANVAS_WIDTH = window.innerWidth - 10;
var CANVAS_HEIGHT = window.innerHeight - 70;
var canvas = document.querySelector('canvas')
var context = canvas.getContext('2d');
canvas.width = CANVAS_WIDTH;
canvas.height = CANVAS_HEIGHT;
context.fillStyle = 'red';

let array = [...Array(80).keys()].reverse();
// skip a draw call here, and
// Don't assign to array, since bubble_Sort now returns a promise
bubble_Sort(array).then(sorted => console.log(...sorted));

<canvas></canvas>

Force redraw during sort function execution in order to animate the steps

Unfortunately there is no way to force a draw, or DOM update, while your thread is still running. The way to solve this is to make your sort algorithm re entrant, so that it can be called from a timer, or via setTimeout. Each time the timer is triggered, you perform one iteration of the sort, and then draw the result.

This is a bit annoying sometimes when studying algorithms by visualizing them, as step visualization cannot be achieved without modifying the algorithm.

EDIT: Added working code snippet that implements a "reentrant" sort.

<html><body><canvas id="myCanvas"   width="300" height="700" style="border:1px solid #d3d3d3;"></canvas><script>function swap(nums, pos1,pos2) { var a = nums[pos1]; nums[pos1] = nums[pos2]; nums[pos2] = a;}function shuffle(nums) { for (var i = 0; i < 1000; i++) {  var num1 = Math.floor((Math.random())*26);  var num2 = Math.floor((Math.random())*26);  swap(nums,num1,num2); }}function sleep(seconds) {  var e = new Date().getTime() + (seconds * 1000);  while (new Date().getTime() <= e) {}}function drawIt(nums) { var c = document.getElementById("myCanvas"); var ctx = c.getContext("2d"); for (var i = 0; i < nums.length; i++) {  var c = document.getElementById("myCanvas");  var ctx = c.getContext("2d");   ctx.beginPath();  ctx.rect(10, i * 20 + 10, 50, 20);  ctx.stroke();  ctx.fillStyle = "rgba(" + nums[i] + ", " + nums[i] + ", " + nums[i] + ", 1)";  ctx.fill(); }}var nums = new Array();for (var i = 0; i<=250; i+=10) { nums[i/10] = i;}shuffle(nums);

function sort(){        var i=0;    var j=0;    var sortComplete=false;    var reentrantSort = function()    {        if (nums[i] > nums[j]){            swap(nums, i, j);            drawIt(nums)        }        j++;        if (j == nums.length){            j=0;i++;            if (i == nums.length ) {                i=0;j=0;                sortComplete=true; //Sorting is done            }        }        if (!sortComplete){ // If sort still not complete            setTimeout(reentrantSort,40); // Run next iteration in 40 ms.        }    };    reentrantSort();}
sort();</script></body></html>

How can I show the process of a Merge Sort similiarly to how I did to a Bubble Sort on canvas

Great code! The issue with displaying this is that it creates copies at each iteration using slice(), so the original array remains the same until the end. Instead of using return statements, just change the actual array. To do this, pass in indexes of the subarrays, then change the actual array. Just call draw(array) within the function. Notice now neither function returns anything, instead they change the array passed in...

async function mergeSort(array, leftIndex, rightIndex) {
    length = rightIndex - leftIndex
    if (length < 2) {
        return array;
    }
    var mid = leftIndex + Math.floor(length / 2);

    mergeSort(array, leftIndex, mid)
    mergeSort(array, mid, rightIndex)      
    await delay(1000*Math.sqrt(rightIndex-leftIndex));
    draw(array)
    merge(array, leftIndex, mid, rightIndex)

}

function merge(array, leftIndex, mid, rightIndex) {
    var result = [];
    var l = leftIndex,
        r = mid;
    while (l < mid && r < rightIndex) {
        if (array[l] < array[r]) {
            result.push(array[l++]);
        } else {
            result.push(array[r++]);
        }
    }
    result = result.concat(array.slice(l, mid)).concat(array.slice(r, rightIndex));
    for (let i = 0; i < rightIndex - leftIndex; i++) {
        array[leftIndex + i] = result[i]
    }
}

Button Script:

<button id="mSort" class="sort" onclick=
"(async() => {
  await mergeSort(cArray,0,360);
  await delay(1600);
  draw(cArray);
})()"
>Merge Sort</button>
</div>

This button script is to allow for the last draw, since the draw occurs before the final merge if you don't await then draw it will be stuck before the final merge...

How to animate multiple HTML5 canvas objects one after another?

Key frames

You can use key frames to great effect to animate almost anything.

The example below (was going to do more of a write up but I was too late, you have accepted an answer) shows how a very basic key frame utility can create animations.

A key frame is just a time and a value

Key frames are added to tracks that give a name to the value.

Thus the name x (position) and the keys {time:0, value:100}, {time:1000, value:900} will change the x property from 100 to 900 during the time 0 to 1 second

For example a circle

const circle = {
    x: 0,
    y: 0,
    r: 10,
    col : "",
    draw() { 
        ctx.fillStyle = this.col;
        ctx.beginPath(); 
        ctx.arc(this.x, this.y, this.r, 0, Math.PI * 2); 
        ctx.fill() 
    }
};

can have any of its properties changed over time.

First create a tracks object and define the keys

const circleTracks = createTracks();

// properties to animate
circleTracks.addTrack("x");
circleTracks.addTrack("y");
circleTracks.addTrack("r");
circleTracks.addTrack("col");

Then add key frames at specific time stamps.

circleTracks.addKeysAtTime(0, {x: 220, y :85, r: 20, col: "#F00"});
circleTracks.addKeysAtTime(1000, {x: 220, y :50, r: 50, col: "#0F0"});
circleTracks.addKeysAtTime(2000, {x: 420, y :100, r: 20, col: "#00F"});
circleTracks.addKeysAtTime(3000, {x: 180, y :160, r: 10, col: "#444"});
circleTracks.addKeysAtTime(4000, {x: 20, y :100, r: 20});
circleTracks.addKeysAtTime(5000, {x: 220, y :85, r: 10, col: "#888"});
circleTracks.addKeysAtTime(5500, {r: 10, col: "#08F"});
circleTracks.addKeysAtTime(6000, {r: 340, col: "#00F"});

When ready clean up the the keys (You can add them out of time order)

circleTracks.clean();

Seek to the start

circleTracks.seek(0);

And update the object

circleTracks.update(circle);

To animate just call the tick and update functions, and draw the circle

circleTracks.tick();
circleTracks.update(circle);
circle.draw();

Example

Click to start the animation.
When it ends you can scrub the animation using tracks.seek(time)

This is the most basic keyframe animations.

And the best thing about key frames is that they separate the animation from the code, letting you import and export animations as simple data structures.

const ctx = canvas.getContext("2d");
requestAnimationFrame(mainLoop);
const allTracks = [];function addKeyframedObject(tracks, object) {    tracks.clean();    tracks.seek(0);    tracks.update(object);    allTracks.push({tracks, object});}const FRAMES_PER_SEC = 60, TICK = 1000 / FRAMES_PER_SEC; //const key = (time, value) => ({time, value});var playing = false;var showScrubber = false;var currentTime = 0;function mainLoop() {    ctx.clearRect(0 ,0 ,ctx.canvas.width, ctx.canvas.height);    if(playing) {        for (const animated of allTracks) {            animated.tracks.tick();            animated.tracks.update(animated.object);        }    }    for (const animated of allTracks) {        animated.object.draw();    }
        if(showScrubber) {            slide.update();        slide.draw();        if(slide.value !== currentTime) {            currentTime = slide.value;            for (const animated of allTracks) {                animated.tracks.seek(currentTime);                animated.tracks.update(animated.object);            }        }            } else {        if(mouse.button) { playing = true }    }    if(allTracks[0].tracks.time > 6300) {         showScrubber = true         playing = false;    }        requestAnimationFrame(mainLoop);}

const text = {    x: canvas.width / 2,    y: canvas.height / 2,    alpha: 1,    text: "",    draw() {         ctx.font = "24px arial";        ctx.textAlign = "center";        ctx.textBaseline = "middle";        ctx.fillStyle = "#000";        ctx.globalAlpha = this.alpha;        ctx.fillText(this.text, this.x, this.y);        ctx.globalAlpha = 1;    }}const circle = {    x: 0,    y: 0,    r: 10,    col : "",    draw() {         ctx.fillStyle = this.col;        ctx.beginPath();         ctx.arc(this.x, this.y, this.r, 0, Math.PI * 2);         ctx.fill()     }}

const circleTracks = createTracks();circleTracks.addTrack("x");circleTracks.addTrack("y");circleTracks.addTrack("r");circleTracks.addTrack("col");
circleTracks.addKeysAtTime(0, {x: 220, y :85, r: 20, col: "#F00"});circleTracks.addKeysAtTime(1000, {x: 220, y :50, r: 50, col: "#0F0"});circleTracks.addKeysAtTime(2000, {x: 420, y :100, r: 20, col: "#00F"});circleTracks.addKeysAtTime(3000, {x: 180, y :160, r: 10, col: "#444"});circleTracks.addKeysAtTime(4000, {x: 20, y :100, r: 20});circleTracks.addKeysAtTime(5000, {x: 220, y :85, r: 10, col: "#888"});circleTracks.addKeysAtTime(5500, {r: 10, col: "#08F"});circleTracks.addKeysAtTime(6000, {r: 340, col: "#00F"});
addKeyframedObject(circleTracks, circle);

const textTracks = createTracks();textTracks.addTrack("alpha");textTracks.addTrack("text");textTracks.addKeysAtTime(0, {alpha: 1, text: "Click to start"});textTracks.addKeysAtTime(1, {alpha: 0});textTracks.addKeysAtTime(20, {alpha: 0, text: "Simple keyframed animation"});textTracks.addKeysAtTime(1000, {alpha: 1});textTracks.addKeysAtTime(2000, {alpha: 0});textTracks.addKeysAtTime(3500, {alpha: 0, text: "The END!" });textTracks.addKeysAtTime(3500, {alpha: 1});textTracks.addKeysAtTime(5500, {alpha: 1});textTracks.addKeysAtTime(6000, {alpha: 0, text: "Use slider to scrub"});textTracks.addKeysAtTime(6300, {alpha: 1});addKeyframedObject(textTracks, text);

function createTracks() {    return {        tracks: {},        addTrack(name, keys = [], value) {              this.tracks[name] = {name, keys, idx: -1, value}        },        addKeysAtTime(time, keys) {            for(const name of Object.keys(keys)) {                this.tracks[name].keys.push(key(time, keys[name]));            }        },        clean() {            for(const track of Object.values(this.tracks)) {                track.keys.sort((a,b) => a.time - b.time);            }        },        seek(time) { // seek to random time            this.time = time;            for(const track of Object.values(this.tracks)) {                if (track.keys[0].time > time) {                    track.idx = -1; // befor first key                }else {                    let idx = 1;                    while(idx < track.keys.length) {                        if(track.keys[idx].time > time && track.keys[idx-1].time <= time) {                            track.idx = idx - 1;                            break;                        }                        idx += 1;                    }                }            }            this.tick(0);        },         tick(timeStep = TICK) {             const time = this.time += timeStep;            for(const track of Object.values(this.tracks)) {                if(track.keys[track.idx + 1] && track.keys[track.idx + 1].time <= time) {                    track.idx += 1;                }                if(track.idx === -1) {                    track.value = track.keys[0].value;                } else {                    const k1 = track.keys[track.idx];                    const k2 = track.keys[track.idx + 1];                    if (typeof k1.value !== "number" || !k2) {                        track.value = k1.value;                    } else if (k2) {                        const unitTime = (time - k1.time) / (k2.time - k1.time);                        track.value = (k2.value - k1.value) * unitTime + k1.value;                    }                 }                            }        },        update(obj) {            for(const track of Object.values(this.tracks)) {                obj[track.name] = track.value;            }        }       };};

const slide = {    min: 0,    max: 6300,    value: 6300,    top: 160,    left: 1,    height: 9,    width: 438,    slide: 10,    slideX: 0,    draw() {                        ctx.fillStyle = "#000";        ctx.fillRect(this.left-1, this.top-1, this.width+ 2, this.height+ 2);        ctx.fillStyle = "#888";        ctx.fillRect(this.left, this.top, this.width, this.height);        ctx.fillStyle = "#DDD";        this.slideX = (this.value - this.min) / (this.max - this.min) * (this.width - this.slide)  + this.left;        ctx.fillRect(this.slideX, this.top + 1, this.slide, this.height - 2);    },        update() {
         if(mouse.x > this.left && mouse.x < this.left + this.width &&             mouse.y > this.top && mouse.y < this.top + this.height) {                        if (mouse.button && !this.captured) {                this.captured = true;            } else {                canvas.style.cursor = "ew-resize";            }         }         if (this.captured) {            if (!mouse.button) {               this.captured = false;               canvas.style.cursor = "default";            } else {               this.value = ((mouse.x - this.left) / this.width) * (this.max - this.min) + this.min;               canvas.style.cursor = "none";               this.value = this.value < this.min ? this.min : this.value > this.max ? this.max : this.value;                           }         }      } };                        const mouse  = {x : 0, y : 0, button : false};function mouseEvents(e){     const bounds = canvas.getBoundingClientRect();    mouse.x = e.pageX - bounds.left - scrollX;    mouse.y = e.pageY - bounds.top - scrollY;    mouse.button = e.type === "mousedown" ? true : e.type === "mouseup" ? false : mouse.button;}["down","up","move"].forEach(name => document.addEventListener("mouse"+name,mouseEvents));

canvas { border: 1px solid black; }

<canvas id="canvas" width="440" height="170"><canvas>

Visualising bubble sort using chart.js

You can use the setTimeout() method and update the labels, dataset.data and dataset.backgroundColor with a certain delay each time array elements are swapped. Then you also need to invoke chart.update() to make sure, Chart.js re-draws the updated chart on the canvas.

Please take a look at the runnable code below and see how it works.

function bubbleSort() {  
  let labels = chart.data.labels;
  let data = chart.data.datasets[0].data;
  let colors = chart.data.datasets[0].backgroundColor;
  let swapped;
  let timeout = 0;
  do {
    swapped = false;
    for (let i = 0; i < data.length; i++) {
      if (data[i] > data[i + 1]) {        
        swap(labels, i);
        swap(data, i);
        swap(colors, i);
        timeout += 50;
        this.updateChartDelayed(labels.slice(0), data.slice(0), colors.slice(0), timeout);
        swapped = true;
      }
    }
  } while (swapped);
}

function swap(arr, i) {
  let tmp = arr[i];
  arr[i] = arr[i + 1];
  arr[i + 1] = tmp;
}

function updateChartDelayed(labels, data, colors, timeout) {
  setTimeout(() => {
    chart.data.labels = labels;
    chart.data.datasets[0].data = data;
    chart.data.datasets[0].backgroundColor = colors;
    chart.update();
  }, timeout);
}

const labels = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];
const chart = new Chart('myChart', {
  type: 'bar',
  data: {
    labels: labels,
    datasets: [{
      data: labels.map(() => Math.random()),
      backgroundColor: ['#FF6633', '#FFB399', '#FF33FF', '#FFFF99', '#00B3E6', '#E6B333', '#3366E6', '#999966', '#99FF99', '#B34D4D', '#80B300', '#809900', '#E6B3B3', '#6680B3', '#66991A',  '#66664D', '#991AFF', '#E666FF', '#4DB3FF', '#1AB399', '#4D8066', '#809980', '#E6FF80', '#1AFF33', '#999933', '#FF4D4D'],
      borderWidth: 1
    }]
  },
  options: {
    legend: {
      display: false
    },
    scales: {
      yAxes: [{
        ticks: {
          beginAtZero: true
        }
      }]
    }
  }
});

setTimeout(() => bubbleSort(), 1000);

<script src="https://cdnjs.cloudflare.com/ajax/libs/Chart.js/2.9.4/Chart.min.js"></script>
<canvas id="myChart" height="90"></canvas>

---

Related Topics