Случайная пересортировка массива

[Gvozd]

Это уже на совести реализаций, как они получают "случайное" число. Зато по коду всё понятно.
Мне известно, что процессор в принципе не может генерировать случайные числа.

Не совсем верные рассуждения.
Случайное число случайному числу рознь, и у них есть ряд качеств и характеристик, по которым вполне определенно можно сказать, ч случайные числа полученные одни алгоритмом лучше других.
Одним из таких качеств/требований является равномерное распределение генерируемых чисел по всему множеству
Есть и более строгие критерии:
http://ru.wikipedia.org/wiki/%D0%A2%...%D1%8B_diehard

Приведу более очевидный пример хорошого и плохого случайного числа(целое от 0 до 2)

var q = [0,0,0];
for(var i = 0; i < 10000; i++) {
    q[Math.floor(Math.random()*2.01)]++
}
console.log(q);

var q = [0,0,0];
for(var i = 0; i < 10000; i++) {
    q[Math.floor(Math.random()*3)]++
}
console.log(q);

[5029, 4923, 48]
[3409, 3301, 3290]

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

[Gvozd]

Что делает функция test?

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

Если более подробно, то пожалуйста:

function test(func) {
	//сюда помещаем количество выпадений того или иного варианта результата
	test_result = {};
	for(var i = 0; i < test_count; i++) {
		var arr = array.slice();
		func(arr);
		if(test_result[arr] == undefined) {
			test_result[arr] = 0;
		}
		//увеличиваем счетчик данного результата
		test_result[arr]++;
	}
	//делаем из объекта test_result массив пар "ключ-значение", для того чтобы можно было отсортировать по ключу
	//сделано из соображений читаемости
	var test_list = [];
	for(var i in test_result) {
		test_list.push([i,test_result[i]]);//ложим пару "ключ-значение"
	}
	min = max = test_result[i];//иницииализируем минимальное и максимальное значение значением последнего элемента
	test_list.sort(function(a,b) {//сортируем test_list по "ключу"
		//попутно определяем максимальное и минимальное значение
		min = Math.min(min, a[1], b[1]);
		max = Math.max(max, a[1], b[1]);
		return a[0] < b[0] ? -1 : 1;
	});
	//выводим упорядочненный массив пар "ключ-значение"
	for(var i =0; i< test_list.length; i++) {
		console.log(test_list[i][0] + ': ' + test_list[i][1]);
	}
	//выводим минимальное и максимальное встреченное значение.
	//Чем они ближе, тем лучше данный алгоритм случайно сортировки.
	//Критерий конечно сильно упрощен, но для задач не связанных с криптографией его вполне можно взять
	console.log([min, max]);
}

[B~Vladi]

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

Не ну конечно будет такой результат, но как это относится к тому, что браузеры генерят случайные числа неравномерно?

[Gvozd]

но как это относится к тому, что браузеры генерят случайные числа неравномерно?

никак не относится.
я этого и не собирался показать.

Я просто взял ГПСЧ браузера, который выдает статистически достаточно равномерную выборку, и путем преобразований получил на его основе случайное число из {0,1,2}
При этом один из алгоритмов преобразований я намеренно взял такой, чтобы получить заведомо неравномерное распределение на выходе, получая равномерное на входе.

Как по-твоему, приведенные мною алгоритмы получения случайного числа из {0,1,2} равноценны, или один из них лучше за счет более равномерного распределения?

Если ответ да, то перенеси этот ответ на сравнение моего и своего алгоритма случайной сортировки.
Твой выдает распределение с большим размахом частот.

При этом для моего алгоритма несложно математически обосновать что при равномерном распределении исходного ГПСЧ, встроенного в браузер, распределение случайных массивов на выходе будет также равномерно.
А для твоего алгоритма такого математического обоснования скорее всего не найдется, и как по мне очевидно, что наоборот результат не будет равномерным. В любом случае обосновывать равномерность, если бы она была, надо для каждого браузера, для каждой имплементации сортировки в каждом браузере

[B~Vladi]

Это не мой алгоритм

[Kolyaj]

браузеры генерят случайные числа неравномерно?

Браузеры генерят числа очень даже равномерно, иначе они были бы бесполезны чуть менее чем полностью. Причина плохого перемешивания в реализации метода sort.

[Gvozd]

Это не мой алгоритм

Ок, приведенный тобой.
Приведенный тобою алгоритм хуже приведенного мною.
Хотя и лучше первого алгоритма

[Kolyaj]

Приведенный тобою алгоритм хуже приведенного мною.
Хотя и лучше первого алгоритма

По моей ссылке способ ещё и быстрее. Насчёт твоего не знаю, splice смущает.

[Gvozd]

По моей ссылке способ ещё и быстрее. Насчёт твоего не знаю, splice смущает.

Так и есть.
Мой способ самый медленный в теме.
Главной целью ставил очевидность его равномерного распределения.

[B~Vladi]

Приведенный тобою алгоритм хуже приведенного мною.

Да вижу я, вижу