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?
EditThe 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");
}