Question 403735 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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

Tags:

2

Answers


  1. 0

    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) ENTIRE ROW (whose index is stored in variable selectionI). And for this row (let’s say it’s row 0), the loop controlled by j will SEQUENTIALLY read all the remaining rows (comparing row 0 to row 1; row 0 to row 2; 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 row 0 with row 1 before comparing row 0 with row 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. 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 ends far BEFORE the beginning of the processing of 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 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 row 0 with row 1; remember, you deleted the internal j loops that were present in selectionSort()). Then, the processing of row 0 ends (for now).

    About 0.1 seconds later, a new job will begin to process row 1, scheduling a new asynchronous job (which will just compare row 1 with row 2). At almost the same time, the second run of the job that compared row 0 with row 1 will compare row 0 with row 2 (the variable selectionJ 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 rows, after N * 0.1 seconds you’ll have N threads running in parallel (not really at the same time, but you get the idea), each one processing just one "main" row vs. another "secondary" row (something like row 0 vs. row 5; row 1 vs. row 5; row 2 vs. row 5; 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 do 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.

    Login or Signup to reply.
  2. 0

    This is a follow up to my previous answer, with a working variant of your selectionSort2() original function. I think it’s pretty self-explanatory. It doesn’t use any loops and it processes one single comparison (arr[J] vs arr[minIndex]) in each scheduled "job". For an array of 6 elements, there will be 5+4+3+2+1 "jobs", running one after another with an interval of 100/1000 seconds between them.

    function selectionSort2bis() {
    // Closure variables (common context)
    let selectionI = 0;
    let selectionJ = selectionI + 1
    let minIndex = selectionI
    
    // Schedule just one job, which will be run once each 100 mseconds.
    const jobHandle = setInterval(() => {
        if (selectionI < arr.length) {         
          if (selectionJ < arr.length) {
              // Look for a new min: compare arr[J] with arr[minIndex]
              console.log ("Comparing arr[" + selectionJ + "] against arr[" + minIndex + "] " + "(" + arr[selectionJ] + " against " + arr[minIndex] + ")");
              if (arr[selectionJ] < arr[minIndex]) {
                  minIndex = selectionJ;
              }
              // Advance J
              selectionJ++;
          }
          else {
              // J is already at the end; swap arr[I] and arr[minIndex]
              if (minIndex != selectionI) {
                  console.log ("- Swapping arr[" + minIndex + "] with arr[" + selectionI + "]" + " (" + arr[minIndex] + " with " + arr[selectionI] + ")");
                  swap(minIndex, selectionI);
              }

              // Advance I; reset J and minIndex
              selectionI++;
              selectionJ = selectionI + 1;
              minIndex = selectionI;
          }
        }
        else {
          // I is already at the end; show the result and cancel the job
          console.log (arr);
          clearInterval(jobHandle);
        }

    }, 100)
}


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

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

selectionSort2bis();

    And this is the output:

    Comparing arr[1] against arr[0] (200 against 100)
Comparing arr[2] against arr[0] (3 against 100)
Comparing arr[3] against arr[2] (4 against 3)
Comparing arr[4] against arr[2] (5 against 3)
Comparing arr[5] against arr[2] (6 against 3)
- Swapping arr[2] with arr[0] (3 with 100)

Comparing arr[2] against arr[1] (100 against 200)
Comparing arr[3] against arr[2] (4 against 100)
Comparing arr[4] against arr[3] (5 against 4)
Comparing arr[5] against arr[3] (6 against 4)
- Swapping arr[3] with arr[1] (4 with 200)

Comparing arr[3] against arr[2] (200 against 100)
Comparing arr[4] against arr[2] (5 against 100)
Comparing arr[5] against arr[4] (6 against 5)
- Swapping arr[4] with arr[2] (5 with 100)

Comparing arr[4] against arr[3] (100 against 200)
Comparing arr[5] against arr[4] (6 against 100)
- Swapping arr[5] with arr[3] (6 with 200)

Comparing arr[5] against arr[4] (200 against 100)

[3, 4, 5, 6, 100, 200]
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search