Блог

Для развлечения я пытаюсь визуализировать алгоритм сортировки, но столкнулся с проблемой.

Я попытался вызвать функцию рисования в методе сортировки, но браузер блокируется и отображает только окончательный отсортированный массив. Как я могу визуализировать каждый процесс сортировки?

 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 Функция должна быть функцией, которая возвращает обещание, которое выполняется с небольшой задержкой.

В качестве примечания, вы можете немного ускорить сортировку пузырьков. Внутренний цикл не должен повторно просматривать часть массива, которая уже отсортирована. Каждый раз, когда внешний цикл выполняет цикл, значение достигает своего конечного места в правом конце массива, поэтому внутренний цикл может остановиться до достижения этой позиции.

Вы также можете немного сэкономить на чертеже: вызывайте только draw при выполнении обмена, так как нет смысла рисовать одну и ту же ситуацию дважды.

Вот ваш код с этими адаптациями:

 // 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>  

Вам не хватает setTimeout , вам нужно установить тайм-аут между каждым изменением вашего массива, чтобы вы действительно могли видеть изменения. В настоящее время все ваши изменения происходят, но слишком быстро, чтобы увидеть 🙂

Это будет что-то вроде:

1. Нарисовать массив
2. Подождите 300 миллисекунд
3. Нарисовать массив
4. Подождите 300 миллисекунд
5. И т.д…

Вам нужно обернуть функцию рисования с помощью setTimeout , вам нужно будет указать число для продолжительности тайм-аута, там вам нужно сделать что-то вроде: 300 * index .

Кроме того, я вижу, что у вас уже есть speed переменная, но вы ее не использовали..