How to do quicksort animation with canvas

Asked

Viewed 48 times

2

I tried redesigning the canvas every time it swaps, but it first renders everything and then draws. I would like each Swap to redesign 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

2 answers

3

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

To turn your code into asynchronous, I had to rewrite the function sleep. Too many functions just added a few keywords async and await where relevant.

The problem is that as the code was synchronous, it ran everything before returning control back to the browser so that it could do its job of redesigning the screen. With asynchronous code, it no longer happens.

I also renamed the constants X and Y for xBase and yBase because I think in function drawGraph mix up names x and X and also y and Y is something that 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>

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

1


The problem is that its 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 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 in a similar way, 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 little more processor resources, since requestAnimationFrame aims to achieve 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>

  • You can complement the code by showing the form that the requestAnimationFrame would be in the code I put in question ??

  • Are you implementing this just for learning, or do you intend to publish it to be used by other people? If this is the first option, you can use async/await, which is already supported by the most modern browsers.

  • Just for real learning.

  • I added the code adapted with async/await. It was very cool its implementation by the way. :)

  • Worked perfectly.

Browser other questions tagged javascript canvas

You are not signed in. Login or sign up in order to post.