Задать вопрос

seventeenroad

Лайки

  • Почему при выносе массива из цикла в глобальную переменную, сортировка имеет разную вероятность?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    DISCLAIMER Реализации сортировки могут быть разными.

    Добавьте в функцию сортировки вывод итерации, a, b и полученного случайного результата.
    spoiler
    { // выполнить в консоли браузера
  const oneTest = () => {
    let iterations = 0;
    [1, 2, 3].sort((a, b) => {
      const result = Math.random() > Math.random() ? 1 : -1;
      console.log(`${iterations}: ${a} vs ${b} = ${result}`);
      iterations++;

      return result;
    });

    return iterations;
  }

  console.clear();
  const totalTests = 10;
  const stats = {};
  
  for (let test = 0; test < totalTests; test++) {
    console.group(`Test ${test + 1} of ${totalTests}`);
    const iterations = oneTest();
    stats[iterations] ??= 0;
    stats[iterations]++;
    console.groupEnd();
  }
  console.log(JSON.stringify(stats, null, 2));
}

    Выводит шаги сортировки. И общую статистику: у меня вышло 5 раз по 3, 5 раз по 2 сравнения из 10.

    Иногда требуется 3 сравнения, если у первых двух разные знаки.
    Иногда достаточно двух, когда у первых двух сравнений знаки совпадают.

    Из этой оптимизации и следует неравномерность результатов, когда начальные условия одни и те же. Вспоминайте теор.вер.
    Ответ написан
    Комментировать
    Комментировать

  • Почему при выносе массива из цикла в глобальную переменную, сортировка имеет разную вероятность?

    Aetae
    @Aetae Куратор тега JavaScript
    Тлен
    В первом случае ты сортируешь уже отсортированный массив повторно(при каждой сортировке начальное состояние разное), во втором ты сортируешь каждый раз новый(начальное состояние одно и то же).

    Использование Math.random в sort в любом случае не даст нормального распределения, т.к. под капотом используется определённый оптимизированный алгоритм сортировки, к тому же браузерозаивисимый и разный для разных случаев.
    Как это всё влияет на конечный результат - одному богу известно (или дотошному математику, который засядет с сырцами браузера и распишет километровые формулы, да).
    Если нормальное распределение получилось на практике - это совпадение, а не гарантия, что так и будет впредь.

    Факт в том, что не надо использовать метод sort ни для чего, кроме его предназначения - детерминированной сортировки.

    Используй нормальный алгоритм перемешивания и будет тебе счастье.
    первый попасшийся вариант
    function shuffle( array ) {	// Shuffle an array
	// 
	// +   original by: Jonas Raoni Soares Silva (http://www.jsfromhell.com)

	for(var j, x, i = array.length; i; j = parseInt(Math.random() * i), x = array[--i], array[i] = array[j], array[j] = x);
	return true;
}
    Ответ написан
    Комментировать
    Комментировать