J'essaye d'utiliser canvas pour visualiser l'algorithme de tri en javascript?

Question

Pour le plaisir, j'essaie de visualiser un algorithme de tri, mais j'ai rencontré un problème.

J'ai essayé d'appeler la fonction de dessin dans la méthode de tri mais le navigateur se verrouille et ne rend que le tableau trié final. Comment visualiser chaque processus de tri?

var CANVAS_WIDTH = window.innerWidth;
var CANVAS_HEIGHT = window.innerHeight;

var canvas = document.querySelector('canvas')
var context = canvas.getContext('2d');

canvas.width = CANVAS_WIDTH;
canvas.height = CANVAS_HEIGHT;

context.fillStyle = 'red';
context.fillRect(0,0, CANVAS_WIDTH, CANVAS_WIDTH);

function draw(array){
    context.save();
    context.clearRect(0, 0, canvas.width, canvas.height);
    context.strokeStyle = 'white';
    context.beginPath();
    context.moveTo(0, canvas.height-100);
    context.lineTo(canvas.width, canvas.height-100);
    context.stroke();
    context.restore();
    context.fillStyle = 'white';
    for(let i = 0; i < array.length; i++){
        context.fillRect(100 + 7*i,canvas.height-100,5,-5 * array[i]);
    }
}




let array = []

for(let i = 0; i < 100; i++){
    array.push(100-i);
}
function bubble_Sort(arr){
    let ticks = 0;  
    const speed = 50;
    let size = arr.length;
    for(let i = 0; i < size; i++){
        ticks++;
        for(let j = 0; j < size - 1; j++){
            draw(array);
            if (arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
draw(array);
array = bubble_Sort(array)

Answer 1

Vous pouvez utiliser async awaitpour cela: de cette façon, vous n'avez pas à toucher (beaucoup) votre code existant. Rendez simplement la fonction bubble_Sort asynchrone avec le mot-clé asyncet ajoutez un await delay()dans la boucle. La delayfonction doit alors être une fonction qui renvoie une promesse qui se résout dans un court délai.

En remarque, vous pouvez accélérer un peu le tri des bulles. La boucle interne ne doit pas revoir la partie du tableau qui est déjà triée. Chaque fois que la boucle externe effectue un cycle, une valeur arrive à son point final à l'extrémité droite du tableau, de sorte que la boucle interne peut s'arrêter avant d'atteindre cette position.

Vous pouvez également économiser un peu sur le dessin: n'appelez que drawlorsque vous effectuez un échange, car il ne sert à rien de dessiner deux fois la même situation.

Voici votre code avec ces 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>

Answer 2

Vous setTimeoutmanquez, vous devez définir un délai entre chaque modification de votre tableau afin que vous puissiez réellement voir le changement. Actuellement, tous vos changements se produisent, mais trop vite pour voir :)

Ça va être quelque chose comme:

1. Dessiner un tableau
2. Attendez 300 millisecondes
3. Dessiner un tableau
4. Attendez 300 millisecondes
5. Etc...

Vous devez envelopper dessiner avec la fonction setTimeout, vous devez spécifier un numéro pour la durée du délai d'attente, il vous faut faire somethink comme: 300 * index.

De plus, je vois que vous avez déjà une speedvariable, mais que vous ne l'avez pas utilisée.