Почему этот алгоритм перемешивания не предвзят

Я нашел причину, по которой это кажется беспристрастным.

Array.sort () не только возвращает массив, но и изменяет сам массив. Если мы повторно инициализируем массив для каждого цикла, мы получим такие результаты, как:

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

Что показывает очень значительную предвзятость.

Для интересующихся вот модифицированный код:

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() { 
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);

Проблема с наивным перемешиванием заключается в том, что значение, возможно, уже было поменяно местами, и вы можете поменять его снова позже. Допустим, у вас есть три карты, и вы выбираете одну наугад для первой карты. Если позже вы сможете случайным образом поменять местами эту карту на последнюю, то вы уберете случайность первого выбора.

Если сортировка является быстрой, она постоянно разбивает список пополам. Следующая итерация случайным образом разбивает каждую из этих групп на две группы. Это продолжается до тех пор, пока у вас не останутся отдельные карты, а затем вы объедините их все вместе. Разница в том, что вы никогда не берете карту из второй случайно выбранной группы и не перемещаете ее обратно в первую группу.

Тасование Кнута-Фишера-Йетса отличается от наивного тасования, потому что вы выбираете карту только один раз. Если бы вы выбирали случайные карты из колоды, вы бы положили карту обратно и выбрали бы снова? Нет, вы берете случайные карты по одной. Я впервые слышу об этом, но я делал нечто подобное еще в старшей школе, начиная с индекса 0 и выше. KFY, вероятно, быстрее, потому что у меня есть дополнительное добавление в случайном операторе.

for (int i = 0; i < cards.Length - 1; i++)
{
  int n = rand.Next(cards.Length - i) + i; // (i to cards.Length - 1)
  Swap(ref cards[i], ref cards[n]);
}

Не думайте об этом как об обмене местами, думайте об этом как о выборе случайных карт из колоды. Для каждого элемента в массиве (кроме последнего, потому что остался только один) вы выбираете случайную карту из всех оставшихся карт и кладете ее, формируя новую стопку карт, которые перемешиваются случайным образом. Не имеет значения, что ваши оставшиеся карты больше не в исходном порядке, если вы уже сделали какую-либо замену, вы все равно выбираете одну случайную карту из всех оставшихся карт.

Случайная быстрая сортировка похожа на то, как если взять стопку карточек и случайным образом разделить их на две группы, затем взять каждую группу и случайным образом разделить ее на две меньшие группы, и так далее, пока у вас не появятся отдельные карточки, а затем снова собрать их вместе.

Собственно, это не реализует его наивную случайную сортировку. Его алгоритм фактически перемещает ключи массива вручную, в то время как sort активно сортирует список.

sort использует quicksort или сортировка вставкой (спасибо cwolves за указание на это - см. Комментарии) для этого (это будет зависеть от реализации):

1. A больше или меньше B? Меньше? Декремент.
2. A больше или меньше C? Меньше? Декремент.
3. A больше или меньше D? Меньше? Вставить A после D
4. B больше или меньше C? Меньше? Декремент.
5. B больше или меньше D? Меньше? Вставить B после D и перед A ...

Это означает, что ваш большой O для среднего случая равен O (n log n), а ваш большой O для худшего случая равен O (n ^ 2) для каждой итерации цикла.

Между тем наивная случайная сортировка Этвуда проста:

1. Начните с A. Найдите случайное значение. Менять.
2. Перейти к Б. Найдите случайное значение. Менять.
3. Перейти к C. Найдите случайное значение. Менять.

(Knuth-Fisher-Yates почти то же самое, только задом наперед)

Таким образом, у него большое значение для худшего случая O (n) и большое O для среднего случая O (n).