javascriptsortingsetinterval

minIndex always = i even after changing its value multiple times?

i'm new to javascript and programming (3 months) and am trying to make a sorting algorithm visualizer like the ones you see on youtube. i had an issue where the for loops usually used were just way to quick to actually visualize so i just replaced the for loops with intervals. this has worked for bubble, insertion, quick and a few other sorting algorithms but i cant for the life of me get selection to work. for some reason when the swap(index1, index2) function is called minIndex and selectionI are always the same. i did the good old console.log and everything seems to work right until the swap function. its been 3 days of suffering and no progress please i need help or pointers

function selectionSort2() {
    let selectionI = 0;
    const selectionIloop = setInterval(() => {
        if(selectionI > arr.length) {
            clearInterval(selectionIloop);
        }
        let minIndex = selectionI;
        let selectionJ = selectionI+1;
        const selectionJloop = setInterval(() => { 
            if(selectionJ > arr.length) {
                clearInterval(selectionJloop);
            }
            if(arr[selectionJ] < arr[minIndex]) {
                minIndex = selectionJ;
            }
            selectionJ++;
        }, 100);
        swap(minIndex, selectionI);
        selectionI++;
    }, 100)
}

i was able to get it partially working by changing the selectionJloop to a for loop like this

function selectionSort() {
    let selectionI = 0;
    const selectionIloop = setInterval(() => {
        if(selectionI > arr.length) {
            clearInterval(selectionIloop);
        }
        let minIndex = selectionI;
        for(let j = selectionI+1; j < arr.length; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        } 
        swap(minIndex, selectionI);
        selectionI++;
    }, 100)
}

but because the for loop doesnt have the 0.1s delay this version has an unfair advantage against the other algorithms whose for loops are restricted. also note that when i put a 0.1s delay inside the for loop as a setTimeout() that it resulted in the same issue as before.

at first i thought that it could be the delay time like the intervals cant have the same delay time but even after changing both of them many many times it just refuses to work.

and just incase heres my swap function:

function swap(index1, index2) {
    temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

i tried changing the interval times to be different from eachother. i tried replacing the intervals with for loops with timeouts instead. i tried completely rewriting it in a different way. whats supposed to happen is minIndex should be the index of the smallest number in the arr whose index isnt less then i+1 but instead minIndex always becomes the same value as i

Solution

  • Edited and expanded. First of all, let's correct your "partially working" selectionSort(). You just have to stop one element before (when selectionI == arr.length). In this example, for an array of 6 elements, valid indexes go from 0 to 5 (then, stop at selectionI == 6).

    function selectionSort() {
    let selectionI = 0;
    const selectionIloop = setInterval(() => {
        if(selectionI >= arr.length) {             // Just changed here!
            console.log (arr);                     // And showed the result
            clearInterval(selectionIloop);
        }
        let minIndex = selectionI;
        for(let j = selectionI+1; j < arr.length; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        } 
        console.log(minIndex, selectionI);
        swap(minIndex, selectionI);
        selectionI++;
    }, 100)
}

function swap(index1, index2) {
    temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

arr = [ 100, 200, 3, 4, 5, 6 ];

selectionSort();

    And the output is:

    2 0
3 1
4 2
5 3
4 4
5 5

[3, 4, 5, 6, 100, 200]

    Let's review this code and see how and why it works (as well as the purely "looped" variant). Your selectionSort() function just schedules a block to be asynchronously (aka. independently) run once each 100/1000 of a second. Then, selectionSort() ends. It doesn't do any "real" processing and it doesn't wait for anything.

    EACH of these (asynchronously run) blocks will process ONE (and just one) set of cells, what I call a "row". The processing of a "row" compares (and could swap) the element at arr[selectionI] with the smallest element present between arr[selectionI+1] and the end of the array. Let's say it's "row" 0 (selectionI==0); the loop controlled by j will SEQUENTIALLY compare cell 0 to cell 1; cell 0 to cell 2; cell 0 to cell 3; etc.

    This sequentiality is key to the success of the entire process. Also crucial is the need to sequentially process each "row". In other words, you MUST compare cell 0 with cell 1 before comparing cell 0 with cell 2; and the entire processing of "row" 0 MUST end before starting the processing of "row" 1.

    A couple of considerations.

    1. JavaScript is single-threaded (except when using "Web Workers"), and jobs scheduled by setInterval() won't overlap. That is, if the processing on one "row" takes more than 0.1 seconds, the processing of the next "row" will begin later than scheduled. Both "rows" will be processed sequentially, and your program should get the correct results. (In this case, it doesn't matter because the processing of each "row" will end long before the time scheduled to process the next "row", as the array is very small and 0.1 seconds is a lot of time, in computer terms.) (Text corrected)

    2. More technical. The selectionI variable (which identifies the current "row") is common to ALL scheduled jobs (ie. all jobs share, read and write the same variable). This is because it's defined at the function level and it's part of something called "closure" (the data context of the function, which is kept alive even when the execution of the function itself ended a long time ago).

    Now, what's going on with your selectionSort2() variant? When the first asynchronous job has to process "row" 0, it just schedules a NEW asynchronous job (which will just compare cell 0 with cell 1; remember: you deleted the internal j loops that was present in selectionSort()). Then, the processing of "row" 0 ends (for now).

    About 0.1 seconds later, the second run of the job that began processing "row" 0 will begin to process "row" 1, scheduling another NEW asynchronous job (which will just compare cell 1 with cell 2).

    At almost the same time, the second run of the job that compared cell 0 with cell 1 will compare cell 0 with cell 2 (the variable selectionJ, the second index, is shared among all instances of this "inner" job, just as selectionI was shared, because it's part of another closure).

    At this point, the much needed sequentiality is completely lost, and it gets worse. At a given time, for an array of N cells (ie. N "rows"), after N * 0.1 seconds you'll have N independent jobs scheduled and running in parallel (not really at the same time, but you get the idea), each one processing just one pair of cells (something like cell 0 vs. cell 5 in one job; cell 1 vs. cell 5 in another; cell 2 vs. cell 5 in another; etc).

    In brief: your selectionSort2() will never work. Your selectionSort() works, with my little correction. Tip: if you just want to delay the execution of a series of purely sequential steps, use await delay(msecs). And if you really want to use an asynchronous approach based on timers, ensure you're running one step at a time, scheduling the start of the next one in a chain.