Почему этот алгоритм сортировки выбора ведет себя так странно
Я наполовину сплю, поэтому я могу что-то упустить из виду, но то, что происходит, очень странно. Я реализовал алгоритм выбора сортировки из Википедии в JavaScript. Вы можете посмотреть код здесь в или на jsbin
Эта проблема
Я заполняю массив циклом for с 10000 случайно сгенерированными числами, потому что требуется много, чтобы показать проблему. Алгоритм работает, как и ожидалось, с любым значением ниже 9800. Однако с 10000 числами и пустым несортированным массивом var unsorted = [];
последние цифры чередуются вот так 9, 10, 9, 10, 9, 10, 9, 10 ...
, Если я инициализирую unsorted
массив по крайней мере с одним элементом, т.е. var unsorted = [1];
, чередующаяся проблема исправлена.
Итак, почему это происходит и почему это происходит, когда несортированный массив содержит не менее 9800 чисел и почему он исправлен, когда я инициализирую несортированный массив хотя бы с одним числом перед заполнением его в цикле for?
редактироватьКажется, проблема не всегда возникает, поэтому, если все выглядит отсортированным с первой попытки, попробуйте еще несколько раз. Кроме того, я протестировал его на Edge, Firefox и Opera с проблемой, возникающей в браузерах. (последние версии на данный момент)
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);
Изменить: тест с C
В этом месяце я изучал C и перевел код, чтобы увидеть, как он ведет себя на другом языке. Ответ - нет проблем. Все отсортировано просто отлично. Вот код для тех, кто любит сравнивать. Это не значит, что мне не интересно понимать, почему проблема возникает в JavaScript, а не в 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");
}