Actual running time of BubbleSort algorithm

Question

I made some tests on BubbleSort algorithm. I firstly entered sorted array then reversely sorted array then randomly sorted array. I run the code for 10000, 100000, and 1000000 input sizes

Here are the results for 1000000 input size:

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

code :

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]);
}

Why does randomly sorted data take more time than reversely sorted data ???

Benchmarking based on one experiment is useless, try to run the experiment a bunch of times (after proper warm-up), and check if the difference is **[statistically significant](http://en.wikipedia.org/wiki/Statistical_significance)**. Also, provide the code you benchmarked, as the answer (if the results are statistically significant) is probably implementation dependent. — amit, Nov 09 '13 at 09:30
It might be caused by the specific way you coded your algorithm, where a randomly sorted array requires more copy operations. Edit your code to count how many times you swap values in the array and see if that correlates with the time taken. — acfrancis, Nov 09 '13 at 09:32
Bubble sort should never be used with large arrays anyway - it's an inefficient algorithm. — Robin Green, Nov 09 '13 at 09:33
Because it takes time to generate the Randomly sorted array. — Kevin Martin Jose, Nov 09 '13 at 09:34
@RobinGreen I suggest removing your comment, this seems like an educational task. (Also, in some cases of almost sorted arrays - bubble sort can be much faster than the nlogn alternatives. — amit, Nov 09 '13 at 09:35
My guess: [branch prediction](http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array/11227902#11227902). — user2357112, Nov 09 '13 at 09:43
@amit: BubbleSort should never be used in production. I consider it a sacking offence! — Mitch Wheat, Nov 09 '13 at 09:46
@amit my point is it seems like an ill-conceived educational task, and that may be a more important lesson than the result of this little experiment. — Robin Green, Nov 09 '13 at 09:46

score 3 · Answer 1 · edited May 23 '17 at 11:44

I'm going to hazard a guess and say it is because of the way you coded your algorithm you are exploiting your CPUs branching prediction. Essentially when you run it on the reverse data, it almost always has to be swapped until it is in the correct position, where as with the random data this is not necessarily the case. Your CPU gets faster when it does predictable things, and slows down on unpredictable things. Random data is unpredictable.

For a better explanation see here: https://stackoverflow.com/a/11227902/1178052

Actual running time of BubbleSort algorithm

1 Answers1