Тест на перетасование кода

Question

Я тестирую код, который я написал, чтобы перетасовать элементы массива. Хотя это не настоящий «профессиональный тест», мне было интересно узнать о результатах.
Я создал случайный массив и продолжал перетасовывать его до тех пор, пока массив не будет отсортирован. Я ожидал, что количество раз, чтобы получить отсортированный порядок, будет вокруг n!/2, и максимальные перетасовки должны быть вокруг n !, где n - количество элементов в массиве.

С 5 элементами количество перетасовки в среднем составляет около 108 и от 6 до 615. Я был удивлен, увидев, что некоторые перетасовки заняли более 500 раз, даже если у меня было всего 5 элементов.

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

void shuffle(int* array, int length) 
{ 
    int i=0; 
    int r =0; 
    for(i=0;i<length;i++) 
    { 
     r = randomInRange(0,i); 
     swap(array,i,r); 
    } 
} 

Answer 1

Почему n!/2? Число перестановок равно n !, поэтому после n! перетасовки, вы только ожидали, что цифры будут правильно упорядочены один раз. Максимальное количество перетасовки - с 5 картами, у вас есть шанс 119/120 получить неуправляемый результат на каждой итерации, и это может продолжаться очень долго.

Вот вывод скрипта Python, я написал, чтобы подсчитать количество раз потребовалось, чтобы правильно угадать случайное число от 1 до 120:

[17, 43, 251, 72, 4, 10, 41, 61, 74, 22, 172, 49, 43, 66, 994, 99, 59, 88, 255, 48] 

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

Однако в вашем случае результаты немного отличаются. Это связано с тем, что вы используете алгоритм перетасовки, который дает искаженные результаты. (Jeff Atwood has written a useful blog post on the subject.)

Я предлагаю вместо этого использовать Fisher-Yates algorithm.