javascriptreactjsalgorithmsortingvisualizer

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

I am making a sorting visualizer in react. With position absolute, I am swapping the transform of the bars. This approach is working fine with BubbleSort but is giving unwanted results in QuickSort. Below is the detailed explanation of the problem.

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

When I swap swapIdx and i swap(blocks[swapIdx], blocks[i]) bars are not swapping in the correct swapIdx as shown in the image below but they are being inserted at the correct position in the DOM.

Image showing bars not swapping in the correct position

Solution

  • Two issues:

    To really swap two DOM elements, proceed as follows: