Как сделать «паузу» во время сортировки слиянием для визуализации JS p5js - PullRequest
1 голос
/ 17 октября 2019

Я работаю над визуализатором сортировки с использованием p5.js, и мне нужно знать, возможно ли замедлить сортировку слиянием, чтобы ее можно было рисовать медленнее. В настоящее время я пытаюсь использовать функцию сна ниже, чтобы замедлить их функцию слияния, но я получаю

Uncaught TypeError: a.slice не является функцией.

Am Iпросто делаю глупую ошибку, или я неправильно подхожу к проблеме?

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));
}

1 Ответ

1 голос
/ 17 октября 2019

Сон внутри вашего алгоритма слияния не имеет никакого смысла. Ваша функция рисования может просто нарисовать окончательный массив, который возвращается mergeSort. Таким образом, даже если вы сделаете алгоритм медленнее, вы не увидите никакого промежуточного звена до тех пор, пока mergeSort не завершится для указанной глубины.

Возможно, будет выполнена сортировка Merge вотдельный поток и для визуализации в draw текущего состояния массива. Но в этом случае вы должны применить сортировку к «оригинальному» массиву, а не создавать копии массива (по slice) и записывать их обратно в исходный массив в конце.

См. Пример:

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