为什么这种方法在可视化反应快速排序时不起作用？

Question

我正在 React 中制作一个排序可视化工具。使用绝对位置，我正在交换条形图的变换。这种方法在 BubbleSort 中运行良好，但在 QuickSort 中会产生不需要的结果。下面是问题的详细解释。

const PIVOT_COLOR = '#FF4949';
const SORTED_COLOR = '#CB6BF9';

async function pivot(blocks, start = 0, end = blocks.length + 1) {
    let pivot = Number(blocks[start].childNodes[0].innerHTML);
    let swapIdx = start;
    let value;

    blocks[start].childNodes[1].style.backgroundColor = PIVOT_COLOR;

    for (let i = start + 1; i < blocks.length; i++) {
        value = Number(blocks[i].childNodes[0].innerHTML);

        blocks[i].childNodes[1].style.backgroundColor = 'blue';

        await new Promise((resolve) =>
            setTimeout(() => {
                resolve();
            }, 500)
        );

        if (pivot > value) {
            swapIdx++;

            let arr = [];
            blocks.forEach(el => arr.push(el.childNodes[0].innerHTML));
            console.log(arr);

            //swap(arr, swapIdx, i);
            await swap(blocks[swapIdx], blocks[i]);
        }

        blocks[i].childNodes[1].style.backgroundColor = SORTED_COLOR;
    }

    await swap(blocks[start], blocks[swapIdx]);
    console.log(swapIdx)
    blocks[start].childNodes[1].style.backgroundColor = SORTED_COLOR;
    return swapIdx;
}

export async function QuickSort(blocks, left = 0, right = blocks.length - 1) {
    if (left < right) {
        let pivotIndex = await pivot(blocks, left, right);
        //left
        await QuickSort(blocks, left, pivotIndex - 1);
        //right
        await QuickSort(blocks, pivotIndex + 1, right);
    }
}

function swap(el1, el2) {
    let wrapper = document.getElementById('wrapper')
    let container = wrapper.childNodes[0];
    return new Promise((resolve) => {
        var temp = el1.style.transform;
        el1.style.transform = el2.style.transform;
        el2.style.transform = temp;

        window.requestAnimationFrame(function () {

            // For waiting for .25 sec
            setTimeout(() => {
                container.insertBefore(el2, el1);
                resolve();
            }, 250);
        });
    });
}

var naming reference

当我交换 swapIdx 和 i swap(blocks[swapIdx], blocks[i]) 条时，它们没有交换正确的 swapIdx，如下图所示，但它们被插入到 DOM.[=14 中的正确位置=]

Image showing bars not swapping in the correct position

Answer 1

两期：

您的代码并没有真正通过调用 insertBefore 来交换 DOM 节点...而是旋转元素在两个给定元素之间的范围内：元素 2 插入在元素 1 之前，这意味着元素 1 和 2 之间出现的所有元素都被移动。
您的 blocks 数组保持不变。那里没有交换任何东西。然而，您还应该交换 blocks 数组中的节点，因为这是您的算法执行比较的基础。

要真正交换两个 DOM 元素，请按以下步骤进行：

创建临时虚拟元素
调用 replaceWith 将该元素交换到文档中，同时取出第一个元素。
调用 replaceWith 将该元素（已取出）与另一个元素交换
调用 replaceWith 将第二个元素与临时元素交换。

为什么这种方法在可视化反应快速排序时不起作用？

Why this approach is not working in visualizing quicksort with react?

javascript

sorting

algorithm

visualizer

reactjs