Фактическое время работы алгоритма BubbleSort

-2

Я провел несколько тестов по алгоритму BubbleSort. Сначала я ввел отсортированный массив, а затем отсортированный по вертикали массив, а затем отсортированный по произвольным данным массив. Я бегу код 10000, 100000 и 1000000 ввода размеровФактическое время работы алгоритма BubbleSort

Ниже приведены результаты по размеру +1000000 ввода:

Sorted array: Actual running time = 304618 ms. 
Reversely sorted array: Actual running time = 742047 ms. 
Randomly sorted array: Actual running time = 1375477 ms.

код:

void BubbleSort (int A[], int size) 
{ 
int i, j; 
for (i=0; i<n-1; i++) 
    for (j=n-1; j>i; j--) 
     if (A[j]<A[j-1]) 
      swap (A[j], A[j-1]); 
}

Почему случайно отсортированные данные занимают больше времени, чем обратные сортированные данные ???

источник

2013-11-09 ammarx

Сравнительный анализ основан на одном эксперименте бесполезно, попробуйте запустить этот эксперимент кучу раз (после надлежащего прогрева), и проверить, если разница ** [статистически значительные] (http://en.wikipedia.org/wiki/Statistical_significance) **. Кроме того, укажите код, который вы проверили, поскольку ответ (если результаты статистически значимы), вероятно, зависит от реализации. – amit

Это может быть вызвано тем, как вы кодировали свой алгоритм, где случайный сортированный массив требует больше операций копирования. Измените свой код, чтобы подсчитать, сколько раз вы меняете значения в массиве и смотрите, соответствует ли это времени. – acfrancis

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

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

Для лучшего объяснения смотрите здесь: https://stackoverflow.com/a/11227902/1178052

источник

2013-11-09 09:40:49

Фактическое время работы алгоритма BubbleSort

ответ

Смежные вопросы