如何“暂停"在合并排序过程中可视化JS p5js [英] How to "pause" during merge sort to visualize JS p5js

问题描述

我正在使用p5.js进行排序可视化程序，我需要知道是否有可能减慢合并排序的速度，以便将其绘制得更慢.我目前正在尝试使用下面的sleep函数来减慢它们的合并功能，但是我得到

Im working on a sorting visualizer using p5.js, and I need to know if its possible to slow down merge sort so it can be drawn slower. Im currently trying to use the sleep function below to slow down they merge function, but I get

未捕获的TypeError:a.slice不是函数.

Uncaught TypeError: a.slice is not a function.

我只是犯了一个愚蠢的错误，还是我错误地解决了这个问题?

Am I just making a silly mistake, or am I approaching the problem incorrectly?

let rectWidth;
let depth = 0;

function setup() {
    let numOfRects = document.getElementById('numOfRects').value;
    let width = document.getElementById('canvas').offsetWidth;
    let height = document.getElementById('canvas').offsetHeight;
    let canvas = createCanvas(width, height);

    rectWidth = floor(width / numOfRects);

    canvas.parent('canvas');
    values = new Array(floor(width / rectWidth));

    for (let i = 0; i < values.length; i++) {
        values[i] = random(height);
    }

    frameRate(1);
}

function draw() {
    background(23);
    values = mergeSort(values, depth);
    depth++;
    for (let i = 0; i < values.length; i++) {
        stroke(0);
        fill(255);
        rect(i * rectWidth, height - values[i], rectWidth, values[i]);
    }

}


function mergeSort(a, d) {
    if (a.length <= 1) {
        return a;
    }

    d--;
    if (d < 1) {
        return (a);
    }
    var mid = Math.round((a.length / 2));
    var left = a.slice(0, mid);
    var right = a.slice(mid);

    let leArr = mergeSort(left, d);
    let riArr = mergeSort(right, d);
    return merge(leArr, riArr);
}

async function merge(left, right) {
    sorted = [];
    while (left && left.length > 0 && right && right.length > 0) {
        if (left[0] <= right[0]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }

    await sleep(50);

    return sorted.concat(left, right);
}

async function sleep(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}

推荐答案

在合并算法中进行睡眠完全没有任何意义.您的draw函数可以绘制由mergeSort返回的最终数组.因此，即使您使算法变慢，在指定深度之前mergeSort都没有完成，您将看不到任何中间产物.

A sleep inside your merge algorithm makes no sense at all. Your draw function can just draw the final array which is returned by mergeSort. So even if you make the algorithm slower, you won't see any intermediate till mergeSort has not finished for the specified depth.

一种可能性是在单独的线程中进行合并排序并在其中可视化draw数组的当前状态.但是在这种情况下，您必须对原始"数组应用排序，而不是创建数组的副本(通过slice)，然后将它们写回到末尾的原始数组中.

A possibility would be to do the Merge sort in a separate thread and to visualize in draw the current state of the array. But in this case you've to apply the sorting on the "original" array, rather than to create copies of the array (by slice) and to write them back to the original array at the end.

请参见示例:

let values = [];
let startSort = true;

function mergeSort(a) {
    // create copy of the array 
    copy = a.slice()
    // asynchronous sort the copy
    mergeSortSlice(copy, 0, copy.length);
    return;
}

async function mergeSortSlice(a, start, end) {
    if (end-start <= 1)
        return;
    
    var mid = Math.round((end+start) / 2);

    // wait till divides are sort 
    await mergeSortSlice(a, start, mid);
    await mergeSortSlice(a, mid, end);

     // merge divides
    let i = start, j = mid;
    while (i < end && j < end) {
        if (a[i] > a[j]) {
            let t = a[j]; a.splice(j, 1); a.splice(i, 0, t);
            j ++;
        }
        i ++;
        if (i==j) j ++;

        // copy back the current state of the sorting
        values = a.slice();
        
        // slow down
        await sleep(100);
    }

    // restart
    if (start == 0 && end == a.length) {
        await sleep(2000);
        startSort = true;
    }
}

async function sleep(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}

function setup() { 
    createCanvas(600, 190);
    frameRate(60);
}

let numOfRects = 15;
let rectWidth;
function draw() {
    if (startSort) {
        startSort = false;
        
        rectWidth = floor(width / numOfRects);
        values = new Array(floor(width / rectWidth));
        for (let i = 0; i < values.length; i++) {
            values[i] = random(height);
        }

        mergeSort(values);
    }

    background(23);
    stroke(0);
    fill(255);
    for (let i = 0; i < values.length; i++) {
        rect(i * rectWidth, height - values[i], rectWidth, values[i]);
    }
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.9.0/p5.js"></script>

这篇关于如何“暂停"在合并排序过程中可视化JS p5js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！