Terminating Bubble Sort Algorithm when the dataset has been sorted

Question

This function goes through the dataset and then sorts it in ascending order.

What its meant to do is stop when the list has been sorted. However, the !changed control flow statement terminates it early, resulting in only one iteration being done. How can I change the code so that the sorting ends when the whole dataset has been sorted?

// Sort the elements using Bubble Sort
function bubble_sort() {
    sort.addEventListener("click", function() {
        const dataList = document.querySelectorAll(".data");
        let delay = 0;

        for (let i = 0; i < dataList.length - 1; i++) {
            let changed  = false
            for (let j = 0; j < dataList.length - 1 - i; j++) {
                setTimeout(() => {
                    let value1 = parseInt(dataList[j].getAttribute("value"));
                    let value2 = parseInt(dataList[j + 1].getAttribute("value"));

                    // Highlight the current pair being compared
                    dataList[j].style.backgroundColor = "blue";
                    dataList[j + 1].style.backgroundColor = "blue";

                    if (value1 > value2) {
                        // Swap the heights and values
                        let tempHeight = dataList[j].style.height;
                        let tempValue = dataList[j].getAttribute("value");

                        dataList[j].style.height = dataList[j + 1].style.height;
                        dataList[j].setAttribute("value", dataList[j + 1].getAttribute("value"));

                        dataList[j + 1].style.height = tempHeight;
                        dataList[j + 1].setAttribute("value", tempValue);
                        changed = true
                    }

                    // Reset the color after comparison
                    setTimeout(() => {
                        dataList[j].style.backgroundColor = "black";
                        dataList[j + 1].style.backgroundColor = "black";
                    }, speed/2);

                }, delay);
                
                delay += speed;
            }
            if (!changed) {
                return;
            }
        }
    });
}

I tried to add a variable to keep track of whether the order has been changed. However, it is checking it early because the changed variable is executed later due to a delay.

I did try to add the setTimeout method:

setTimeout(() => {
    console.log(changed)
    if (!changed) {
        return;
    }
}, (dataList.length - i - 1) * delay);

but to no avail (maybe because my math was wrong)?

Answer 1

The problem is that setTimeout unlike sleep in Python, just schedules the code inside it to run after a certain delay, but by the time it executes the code has already finished. This can lead to unexpected behaviors.

To solve this we can convert the loop into an async function and use await with setTimeout to control the timing. This way the code execution will be paused for the specific duration:

// Helper function to create a delay
function sleep(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}

// Sort the elements using Bubble Sort
async function bubble_sort() {
    sort.addEventListener("click", async function() {  // async function here
        const dataList = document.querySelectorAll(".data");

        for (let i = 0; i < dataList.length - 1; i++) {
            let changed = false;
            for (let j = 0; j < dataList.length - 1 - i; j++) {
                let value1 = parseInt(dataList[j].getAttribute("value"));
                let value2 = parseInt(dataList[j + 1].getAttribute("value"));

                // Highlight the current pair being compared
                dataList[j].style.backgroundColor = "blue";
                dataList[j + 1].style.backgroundColor = "blue";

                if (value1 > value2) {
                    // Swap the heights and values
                    let tempHeight = dataList[j].style.height;
                    let tempValue = dataList[j].getAttribute("value");

                    dataList[j].style.height = dataList[j + 1].style.height;
                    dataList[j].setAttribute("value", dataList[j + 1].getAttribute("value"));

                    dataList[j + 1].style.height = tempHeight;
                    dataList[j + 1].setAttribute("value", tempValue);
                    changed = true;
                }

                await sleep(speed); // Wait for 'speed' milliseconds

                // Reset the color after comparison
                dataList[j].style.backgroundColor = "black";
                dataList[j + 1].style.backgroundColor = "black";

                await sleep(speed / 2); // Wait before resetting the colors
            }
            if (!changed) {
                break;
            }
        }
    });
}

• See this codepen for a demonstration.