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

Viewed 82

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

1 Answers

Two issues:

  • Your code is not really swapping the DOM nodes with a call to insertBefore... Instead it rotates the elements that are in the range between the two given elements: element 2 is inserted before element 1, and that means that all elements that occured between element 1 and 2 are shifted.

  • Your blocks array is left unchanged. Nothing is swapped there. Yet you should also swap the nodes in the blocks array, as that is the basis for your algorithm to perform comparisons.

To really swap two DOM elements, proceed as follows:

  • create temporary dummy element
  • call replaceWith to swap that element into the document and at the same time take the first element out.
  • call replaceWith to swap that element (which was taken out) with the other element
  • call replaceWith to swap the second element with the temporary element.
Related