Почему этот алгоритм сортировки выбора ведет себя так странно

Я наполовину сплю, поэтому я могу что-то упустить из виду, но то, что происходит, очень странно. Я реализовал алгоритм выбора сортировки из Википедии в 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");
}

0 ответов

Другие вопросы по тегам