Problem with animation of a sort algorithm

Asked

Viewed 121 times

2

Good evening, I’m looking to do a simple bar animation of the sort algorithm bubblesort using canvas of html together with javascript but for some reason the bars don’t change position, as if they don’t have Bubble. What did I miss or implement wrong? Thank you

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
    </head>
    <body>
        <canvas id ="bubble" width="500" height="500" style="border: 1px solid #c6c6c6"></canvas>
        <>

            function random(min, max) {
                return Math.random() * (max - min) + min;
            }

            var Barra = function(){
                let numero
                let posX
                let posY
                let altura
                let largura
                let ctx

                this.setNumero = function(_numero){
                    this.numero = _numero
                }

                this.setPosX = function(_posX){
                    this.posX = _posX
                }

                this.setPosY = function(_posY){
                    this.posY = _posY
                }

                this.setAltura = function(_altura){
                    this.altura = _altura
                }

                this.setLargura = function(_largura){
                    this.largura = _largura 
                }

                this.setCtx = function(){
                    this.ctx = c.getContext("2d")
                }                
            }

            let c = document.getElementById("bubble")

            let vet = []
            let soma = 0
            for(let i = 0; i <= 10; i++){
                vet[i] = new Barra()
                let num = Math.floor(random(1,100))
                vet[i].setNumero(num)
                vet[i].setPosX(soma)
                soma += 10
                vet[i].setPosY(0)
                vet[i].setAltura(num + 100)
                vet[i].setLargura(50)
                vet[i].setCtx()
                vet[i].ctx.fillStyle = "red"
                vet[i].ctx.fillRect(vet[i].posX,vet[i].posY,vet[i].largura,vet[i].altura)
            }

            function bubble(vet){
                let aux = 0 
                for(let i = 0; i < vet.length; i++){
                    for(let j = 0; j < (vet.length - 1); j++){
                        if(vet[j].numero > vet[j + 1].numero){                    
                            vet[j].posX = vet[j].posX
                            vet[j + 1].posX = vet[j + 1]
                            vet[j].ctx.fillRect(vet[j].posX,vet[j].posY,vet[j].largura,vet[j].altura)
                        }
                    }
                }
            }
            bubble(vet)
        </>
    </body>
</html>

  • In your local code you even left the script tags empty ? <> and here </>

1 answer

3


Visual problem

In the browser Javascript executes the code in context and single thread(Single Thread) and canvas does not have a method to force visual updates(redraw type), this implies that any graphical changes you make in the context of an object canvas within a loop will only be displayed after the loop is completed.

In your code there were also empty tags <> and </> which are probably the tags <script> and </script>.

Visual Solution

To circumvent this feature of the language you can reshape your code so that instead of relying on a loop for to perform graphic operations, these operations are done repeatedly within a request by animation boards. This request is made by the method 'window.requestAnimationFrame()'

The method 'window.requestAnimationFrame()' informs the browser that an animation is desired and requires the browser to call a specific function to update an animation frame before the next repeat.

function random(min, max) {
    return Math.random() * (max - min) + min;
}

var Barra = function() {
    let numero
    let posX
    let posY
    let altura
    let largura
    let ctx

    this.setNumero = function(_numero) {
        this.numero = _numero
    }

    this.setPosX = function(_posX) {
        this.posX = _posX
    }

    this.setPosY = function(_posY) {
        this.posY = _posY
    }

    this.setAltura = function(_altura) {
        this.altura = _altura
    }

    this.setLargura = function(_largura) {
        this.largura = _largura 
    }

    this.setCtx = function() {
        this.ctx = c.getContext("2d")
    }                
}

let c = document.getElementById("bubble")

let vet = []
let soma = 0
let i = 0 // contador para quantidade de operações a ser realizadas

// Por recomendação do @fernandosavio converti o laço for em uma função que é
//passada como parâmetro para uma requisição de quadros de animação feita
//através do método window.requestAnimationFrame()
function exibirBarras() {
    vet[i] = new Barra()
    let num = Math.floor(random(1,100))
    vet[i].setNumero(num)
    vet[i].setPosX(soma)
    soma += 51
    vet[i].setPosY(0)
    vet[i].setAltura(num + 100)
    vet[i].setLargura(50)
    vet[i].setCtx()
    vet[i].ctx.fillStyle = "red"
    vet[i].ctx.fillRect( 
                        vet[i].posX,
                        vet[i].posY,
                        vet[i].largura,
                        vet[i].altura)            
    i++; // incrementa o contador
    //verifica se o contador atingiu o limite determinado
    if (i < 8) requestAnimationFrame(exibirBarras); // Se ainda não atingir o limite faz a requisição de um novo quadro de animação
}

requestAnimationFrame(exibirBarras);
<canvas id ="bubble" width="500" height="500" style="border: 1px solid #c6c6c6"></canvas>

Problem with Bubble Sort

The Bubble Sort, or floating ordering (literally "per bubble"), is a simpler sort algorithm. The idea is to traverse the vector several times, and with each passage to float to the top the largest element of the sequence. This drive resembles the way bubbles in a water tank look for their own level, and from this comes the name of the algorithm.

In the best case, the algorithm executes n relevant operations, where n represents the number of vector elements. In the worst case, they are made operations. The complexity of this algorithm is quadratic. Therefore, it is not recommended for programs that need speed and operate with high amount of data.

The Bubble Sort algorithm is this one:

faça
    declare :trocado falso
    para cada elemento no vetor até o penúltimo faça
      se os elementos não estão na ordem certa 
         trocar elementos de lugar
         atribua verdadeiro para :trocado
      fim se
    fim para
fim faça se :trocado for falso

Canvas problem and dynamic interaction

The HTML element <canvas> is an element that can be used to draw graphics via code (usually Javascript). For example, it can be used to draw graphics, compose photos, create animations, or even process or render video in real time. It can be done but when it comes to associating objects and values with images the canvas is not very suitable because it tends to become laborious to make associations between values and graphics because after drawing the elements are only pixels in the media (or in a pixel array).

For this type of interaction me I find it easier to use SVG.

Answer

What I did was change the canvas by a svg so that the change of the position of the elements becomes easier, I implemented a correct algorithm of Bubble Sort and also added in Barra a method to facilitate the exchange of properties.

function random(min, max) {
    return Math.random() * (max - min) + min;
}

var Barra = function() {
    let numero
    let posX
    let posY
    let altura
    let largura
    //let ctx
    let rect

    // Troca as propriedades de dois elementos
    this.trocar = function(elem) {
        var aux = this.numero;
        this.numero = elem.numero;
        elem.numero = aux;

        aux = this.posX;
        this.posX = elem.posX;
        elem.posX = aux;

        aux = this.altura;
        this.altura = elem.altura;
        elem.altura = aux;


        this.rect.setAttribute('height',this.altura);
        elem.rect.setAttribute('height',elem.altura);

    }

    this.setNumero = function(_numero) {
        this.numero = _numero
    }

    this.setPosX = function(_posX) {
        this.posX = _posX
    }

    this.setPosY = function(_posY) {
        this.posY = _posY
    }

    this.setAltura = function(_altura) {
        this.altura = _altura
    }

    this.setLargura = function(_largura) {
        this.largura = _largura 
    }

    this.setCtx = function() {
        // this.ctx = c.getContext("2d")
    }          

    this.setRect = function(_rect) {
        this.rect = _rect
    }
}

let c = document.getElementById("bubble")

let vet = []
let soma = 0
let i = 0 
let svgns = "http://www.w3.org/2000/svg";

function exibirBarras() {           
    vet[i] = new Barra()
    let num = Math.floor(random(1,100))
    vet[i].setNumero(num)
    vet[i].setPosX(soma)
    soma += 51
    vet[i].setPosY(0)
    vet[i].setAltura(num)
    vet[i].setLargura(50)

    //Cria um retangulo em SVG
    vet[i].setRect(document.createElementNS(svgns, 'rect'));
    vet[i].rect.setAttributeNS(null, 'x', vet[i].posX);
    vet[i].rect.setAttributeNS(null, 'y', vet[i].posY);
    vet[i].rect.setAttributeNS(null, 'height', vet[i].altura);
    vet[i].rect.setAttributeNS(null, 'width', vet[i].largura);
    vet[i].rect.setAttributeNS(null, 'fill', 'red');
                        
    //Adiciona o retangulo ao elemento bubble
    document.getElementById('bubble').appendChild(vet[i].rect);

    i++;
    if (i > 8){        
        bubble(vet);
    } else {
       requestAnimationFrame(exibirBarras);
    }
}    

requestAnimationFrame(exibirBarras);

// Algoritimo de bubble sort segundo o algoritimo já descrito
function bubble(vet) {
    var aux;
    do {
        var trocado = false;
        for(let i = 0; i < vet.length - 1; i++) {
            vet[i].rect.setAttribute('fill', 'blue');

            if (vet[i].numero > vet[i + 1 ].numero) {
                vet[i].trocar(vet[i + 1 ]);
                trocado = true;
            }
            vet[i].rect.setAttribute('fill', 'red');
        }
    } while (trocado);
}
<svg id ="bubble" width="500" height="500" style="border: 1px solid #c6c6c6"></svg>

  • 1

    It would be interesting for you to talk about window.requestAnimationFrame() where you talk about setInterval... For the sake of good practice and for the AP to know better ways to animate something in JS.

  • @fernandosavio, Thank you!! I didn’t know the method windows.requestAnimationFrame() I will read the documentation, understand how it works and I will definitely fit in the answer.

  • 1

    Oops. I’m glad I could contribute then :D

  • @fernandosavio, Here is the updated response with your recommendation. Again thank you for the information shared.

  • 1

    I thank you very much for the answer Augusto Vasques, exclaimed many doubts that I was having. Thank you!

Browser other questions tagged

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