How to do animation in quicksort with canvas

Question

How to do animation in quicksort with canvas

Navigation

#1 by (3 votes)
#2 by (1 votes)

2

I tried to redraw the canvas every time it swaps, but it first renders everything and then draws. I would like every Swap to redraw the canvas with the object information.

<!DOCTYPE html>
<html>
    <head>
        <script
          src="https://code.jquery.com/jquery-3.2.1.min.js"integrity="sha256-hwg4gsxgFZhOsEEamdOYGBf13FyQuiTwlAQgxVSNgt4="
          crossorigin="anonymous"></script>

        <style type="text/css">
            body{
                margin: 0;
            }
        </style>
    </head>

    <body>
        <canvas id="canvas" class="canvas" width="1400" height="750">
        </canvas>
    </body>
</html>

<script type="text/javascript">
    const Y = 700;
    const X = 50;
    const size = 10; 
    const max_rand = 60;
    const canvas = document.getElementById('canvas');
    const ctx = canvas.getContext('2d');


    $(document).ready(function(){
        var numbers = [];

        for (var i = 0; i < 121; i++) {
            numbers.push({number: Math.random() * max_rand, color: getRandomColor()});
        }
        
        drawGraph(numbers);

        sleep(200);

        quickSort(numbers, 0, numbers.length-1); 
    });

    function drawGraph(numbers){
        ctx.clearRect(0, 0, canvas.width, canvas.height);

        var x = X;
        var y = Y;

        for (var i = 0; i < numbers.length; i++) {
            ctx.fillStyle = numbers[i].color;

            for (var j = 0; j < numbers[i].number; j++) {
                ctx.fillRect(x, y, size, size);

                y -= size;
            }

            x += size;
            y = Y;
        }
    }

    function sleep(miliseconds) {
       var currentTime = new Date().getTime();

       while (currentTime + miliseconds >= new Date().getTime()) {
       }
    }

    function quickSort(numbers, left, right) {
        var index;

        if (numbers.length > 1) {

            index = partition(numbers, left, right);

            if (left < index - 1) {
                quickSort(numbers, left, index - 1);
            }

            if (index < right) {
                quickSort(numbers, index, right);
            }

        }

        return numbers;
    }

    function swap(numbers, firstIndex, secondIndex){
        var temp = numbers[firstIndex].number;
        numbers[firstIndex].number = numbers[secondIndex].number;
        numbers[secondIndex].number = temp;

        drawGraph(numbers);
        sleep(50);
    }

    function partition(numbers, left, right) {

        var pivot   = numbers[Math.floor((right + left) / 2)].number,
            i       = left,
            j       = right;


        while (i <= j) {

            while (numbers[i].number < pivot) {
                i++;
            }

            while (numbers[j].number > pivot) {
                j--;
            }

            if (i <= j) {
                swap(numbers, i, j);
                i++;
                j--;
            }
        }

        return i;
    }

    function getRandomColor() {
        var letters = '0123456789ABCDEF';
        var color = '#';
        for (var i = 0; i < 6; i++) {
            color += letters[Math.floor(Math.random() * 16)];
        }
        return color;
    }
</script>

javascript canvas

asked by anonymous 22.10.2017 / 21:21

2 answers

3

I was able to solve using the concept of asynchronous functions .

To turn your code into asynchronous, I had to rewrite the sleep function. The other functions were to only add some keywords async and await where pertinent.

The problem is that since the code was synchronous, it executed everything before returning the control back to the browser so that it could do its job of redrawing the screen. With the asynchronous code, this is no longer the case.

I've also renamed the X and Y f constants to xBase and yBase because I think that in the drawGraph function, mixing names x and X and also y and Y is something which tends to generate a lot of confusion.

const yBase = 700;
const xBase = 50;
const size = 10; 
const max_rand = 60;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

$(document).ready(function() {
    var numbers = [];

    for (var i = 0; i < 121; i++) {
        numbers.push({number: Math.random() * max_rand, color: getRandomColor()});
    }

    drawGraph(numbers);
    quickSort(numbers, 0, numbers.length - 1);
});

function drawGraph(numbers) {
    ctx.clearRect(0, 0, canvas.width, canvas.height);

    var x = xBase;
    var y = yBase;

    for (var i = 0; i < numbers.length; i++) {
        ctx.fillStyle = numbers[i].color;

        for (var j = 0; j < numbers[i].number; j++) {
            ctx.fillRect(x, y, size, size);

            y -= size;
        }

        x += size;
        y = yBase;
    }
}

function sleep(miliseconds) {
    return new Promise(resolve => {
        setTimeout(resolve, miliseconds);
    });
}

async function quickSort(numbers, left, right) {
    if (numbers.length > 1) {

        var index = await partition(numbers, left, right);

        if (left < index - 1) {
            await quickSort(numbers, left, index - 1);
        }

        if (index < right) {
            await quickSort(numbers, index, right);
        }

    }
    return numbers;
}

async function swap(numbers, firstIndex, secondIndex, next) {
    var temp = numbers[firstIndex].number;
    numbers[firstIndex].number = numbers[secondIndex].number;
    numbers[secondIndex].number = temp;

    drawGraph(numbers);
    await sleep(50);
}

async function partition(numbers, left, right) {

    var pivot   = numbers[Math.floor((right + left) / 2)].number,
        i       = left,
        j       = right;

    while (i <= j) {

        while (numbers[i].number < pivot) {
            i++;
        }

        while (numbers[j].number > pivot) {
            j--;
        }

        if (i <= j) {
            await swap(numbers, i, j);
            i++;
            j--;
        }
    }

    return i;
}

function getRandomColor() {
    var letters = '0123456789ABCDEF';
    var color = '#';
    for (var i = 0; i < 6; i++) {
        color += letters[Math.floor(Math.random() * 16)];
    }
    return color;
}

body {
    margin: 0;
}

<script src="https://code.jquery.com/jquery-3.2.1.min.js"></script><canvasid="canvas" class="canvas" width="1400" height="750">
</canvas>

22.10.2017 / 23:31

Copy (cp) to the current folder in LINUX [closed] How to include current date in a generated JavaDoc?

score 1 · Accepted Answer

The problem is that your sleep function blocks the thread, preventing the browser from processing anything else (rendering or events). This is because JavaScript is by nature monothread.

You can work around this by using the setTimeout function, which accepts a callback and a number of milliseconds that will be expected to call the callback. Another option is setInterval, which works similarly, but the function runs multiple times.

You can also use the requestAnimationFrame function, and check if the minimum time since the last rendering has passed, but this solution requires a bit more processor resources, since requestAnimationFrame aims to reach 60 frames per second.

Solution using async:

<!DOCTYPE html>
<html>
    <head>
        <script
          src="https://code.jquery.com/jquery-3.2.1.min.js"integrity="sha256-hwg4gsxgFZhOsEEamdOYGBf13FyQuiTwlAQgxVSNgt4="
          crossorigin="anonymous"></script>

        <style type="text/css">
            body{
                margin: 0;
            }
        </style>
    </head>

    <body>
        <canvas id="canvas" class="canvas" width="1400" height="750">
        </canvas>
    </body>
</html>

<script type="text/javascript">
    const Y = 700;
    const X = 50;
    const size = 10; 
    const max_rand = 60;
    const canvas = document.getElementById('canvas');
    const ctx = canvas.getContext('2d');

    async function run() {
        var numbers = [];

        for (var i = 0; i < 121; i++) {
            numbers.push({number: Math.random() * max_rand, color: getRandomColor()});
        }

        drawGraph(numbers);

        await sleep(200);

        await quickSort(numbers, 0, numbers.length-1); 
    }

    $(document).ready(function(){
        run();
    });

    function drawGraph(numbers){
        ctx.clearRect(0, 0, canvas.width, canvas.height);

        var x = X;
        var y = Y;

        for (var i = 0; i < numbers.length; i++) {
            ctx.fillStyle = numbers[i].color;

            for (var j = 0; j < numbers[i].number; j++) {
                ctx.fillRect(x, y, size, size);

                y -= size;
            }

            x += size;
            y = Y;
        }
    }

    async function sleep(miliseconds) {
        return new Promise(function (resolve, reject) { setTimeout(resolve, miliseconds) });
    }

    async function quickSort(numbers, left, right) {
        var index;

        if (numbers.length > 1) {

            index = await partition(numbers, left, right);

            if (left < index - 1) {
                await quickSort(numbers, left, index - 1);
            }

            if (index < right) {
                await quickSort(numbers, index, right);
            }

        }

        return numbers;
    }

    async function swap(numbers, firstIndex, secondIndex){
        var temp = numbers[firstIndex].number;
        numbers[firstIndex].number = numbers[secondIndex].number;
        numbers[secondIndex].number = temp;

        drawGraph(numbers);
        await sleep(50);
    }

    async function partition(numbers, left, right) {

        var pivot   = numbers[Math.floor((right + left) / 2)].number,
            i       = left,
            j       = right;


        while (i <= j) {

            while (numbers[i].number < pivot) {
                i++;
            }

            while (numbers[j].number > pivot) {
                j--;
            }

            if (i <= j) {
                await swap(numbers, i, j);
                i++;
                j--;
            }
        }

        return i;
    }

    function getRandomColor() {
        var letters = '0123456789ABCDEF';
        var color = '#';
        for (var i = 0; i < 6; i++) {
            color += letters[Math.floor(Math.random() * 16)];
        }
        return color;
    }
</script>