我正在尝试使用画布来可视化JavaScript中的排序算法？ [英] I am trying to use canvas to visualize sort algorithm in javascript?

问题描述

出于娱乐目的，我试图可视化排序算法，但遇到了问题。

For fun I am trying to visualize a sorting algorithm, but I have run into an issue.

我试图在sort方法中调用draw函数，但浏览器锁定并仅呈现最终排序的数组。如何可视化排序的每个过程？

I tried to call the draw function in the sort method but the browser locks up and renders only the final sorted array. How can I visualize every process of sorting?

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)

推荐答案

您可以使用 async await 进行此操作：这样，您就不必触摸（很多）现有代码。只需使bubble_Sort函数与关键字 async 异步，然后在循环中添加 await delay（）即可。 delay 函数应该是一个返回可在短时延迟内解决的承诺的函数。

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.

您还可以保存绘图上的一点点：执行交换时仅调用 draw ，因为两次绘制相同情况没有用。

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>

这篇关于我正在尝试使用画布来可视化JavaScript中的排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！