3

I am half asleep so I may be overlooking something over here but what is happening is very odd. I implemented the Selection Sort algorithm from Wikipedia in JavaScript. You can view the code here under or at jsbin

The Problem

I am populating an array with a for loop with 10000 randomly generated numbers because it takes that many to show the issue. The algorithm works as expected with anything under 9800. However, with 10000 numbers and an empty unsorted array var unsorted = []; the last numbers are alternating like this 9, 10, 9, 10, 9, 10, 9, 10 .... If I initialize the unsorted array with at least one element i.e var unsorted = [1];, the alternating problem is fixed.

So, why is this happening and why is it happening when the unsorted array contains at least 9800 numbers and why is it fixed when i initialize the unsorted array with at least one number before populating it through the for loop?

Edit

The problem doesn't seem to always happen so if everything looks sorted the first time you try, then try a few more times. Also, i've tested it on Edge, Firefox and Opera with the problem occurring across browsers. (latest versions as of now)

var unsorted = [];

for (let i = 0; i < 10000; i++) {
  unsorted[i] = Math.floor(Math.random() * 11);
}

for (let j = 0; j < unsorted.length; j++) {
  let min = j;

  for (let i = j + 1; i < unsorted.length; i++) {
    if (unsorted[i] < unsorted[min]) {
      min = i;
    }
  }

  if (min != j) {
    [unsorted[j], unsorted[min]] = [unsorted[min], unsorted[j]]
  }
}

console.log(unsorted);

Edit: A Test With C

I've been learning C this month and i translated the code to see how it behaves in a different language. The answer - there is no problem. Everything is sorted just fine. Here is the code for those who like to compare. This does not mean that i am not interested in understanding why the problem happens in JavaScript and not in C.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
    int arrLen = 10000;
    int unsorted[arrLen];
    time_t t;
    srand((unsigned) time(&t));

    for (int i = 0; i < arrLen; i++)
    {
        unsorted[i] = rand() % 11;
    }

    for (int j = 0; j < arrLen; j++)
    {
        int min = j;

        for (int i = j + 1; i < arrLen; i++)
        {
            if (unsorted[i] < unsorted[min]) {
                min = i;
            }
        }

        if (min != j)
        {
            int tmp = unsorted[j];
            unsorted[j] = unsorted[min];
            unsorted[min] = tmp;
        }
    }

    for (int a = 0; a < arrLen; a++)
    {
        printf("%d-", unsorted[a]);
    }
    printf("\n");
}
Dani
  • 59
  • 1
  • 7
  • I don't see the problem in the stack snippet here, or if I clone your jsbin. – Barmar Jan 10 '18 at 20:05
  • Weird, I got the correct answer when I first cloned it, but then when I re-run it the answer is wrong. – Barmar Jan 10 '18 at 20:08
  • Sorry, the snippet and the JSBin were set to loop 9800 times which wont show the problem. The loop needs to loop 10000 times for the problem to show. I changed it now in the code snipped above and in the JSBin. – Dani Jan 10 '18 at 20:10
  • I still don't see the problem here, but I was seeing it in jsbin with 9800. – Barmar Jan 10 '18 at 20:12
  • What browser are you using? – Bergi Jan 10 '18 at 20:19
  • Chrome Version 63.0.3239.132 (Official Build) (64-bit) – Dani Jan 10 '18 at 20:21
  • Perhaps the problem is not the code, but rather the console output, as in https://stackoverflow.com/questions/24175017/google-chrome-console-log-inconsistency-with-objects-and-arrays – Me.Name Jan 10 '18 at 20:23
  • @Me.Name No, the array is logged after all modifications – Bergi Jan 10 '18 at 20:24
  • Try with `console.log(unsorted.slice(-20).join(','))` and see if you still get the same strange result. (NB: I cannot reproduce this in Chrome 63.0 , nor in FF 57.0.4) – trincot Jan 10 '18 at 20:25
  • @Bergi Ah you're right, the provided link isn't accurate for this problem, but the logging still seems to be the culprit. Did some testing and Firefox didn't have the problem. In Chrome it did occur, but only with the current combination of `var`s and `let`s, as if Chrome optimizes in such a way that the console output occurs for the loop is completely finishes. Also adding an extra console.log eleminated the problem (e.g. tried logging the actual value of the last index). – Me.Name Jan 10 '18 at 20:26
  • Also accessing the array after the loop seems to negate the problem. e.g. `let last = unsorted[9999];`. Perhaps Chrome thinks it can safely start logging of the `var` because all loops are local. Huge speculation here, but also making the initial declaration `let unsorted=[]` (and leaving the rest of the code unaltered) produced the correct results – Me.Name Jan 10 '18 at 20:30
  • Ok, adding *any* code after the loops produces the correct results. Logging indeed seems to follow its own timetable – Me.Name Jan 10 '18 at 20:35
  • My guess would be that the optimiser has a bug related to the destrucuring with property targets, and it only kicks in with enough iterations. – Bergi Jan 10 '18 at 20:37
  • Thank you both for looking into this. So its a problem with Chrome's console. Meanwhile i translated the code into C to see :) if the problem occurs in a different language and it doesn't. Thank you all once more. – Dani Jan 10 '18 at 20:49

0 Answers0