Thread: optimizing bubble sort

[latest edit]
A test of adv_bubble, duff_bubble and salem_bubble at the university on a Sun UltraSparc 5 was quite amazing:

gcc 2.95.3 no optimizations:

adv_bubble 4346 ms
duff_bubble 3381 ms
salem_bubble 5633 ms

On the Intel Plattform (P3) adv_ and duff_bubble perform about the same and salem_bubble is the fastest function.

With -O2 turned on (UltraSparc) adv_ and duff_bubble perform about the same again (~1750 ms) and salem_bubble is back on the top with ~1350ms.

I wonder if it is the architecture or the compiler that's making the difference ?
[/latest edit]

> gettimeofday(&start,NULL);
I'd check the return result, to make sure the function was successful

The function was not successful. I don't know why. It was working before, but after implementing Duff's device the clock has gone mad. Maybe the Duff-sort now somehow changes data out of the bounds of the array. I will check this.

Still, your program is working wonderfully as you can see in my posting above.

[edit]
Hmm ... I don't think, that the Duff-sort is related to the gettimeofday-problem, because the first time check is done before duff_bubble is called.
But what could be the error source?
[/edit]
[edit]
The Duff-sort function was the problem. I forgot to adjust the array length and to change from post- to preincrement. The gettimeofday function still returns an error but the time display seems to be okay.
[/edit]

I've found a little bug in the outer loop. It must be
while(--counter)

and NOT while(counter--)

I've discovered this bug, after I've removed the variable "test" and "if(test) return 1;".
The Duff-sort is without this testing even faster than my adv bubble sort with testing removed, too.

• cygwin gcc 3.2 unoptimized
  Qsort time=6165706
  bubble_reference time=1333714207
  bubble_sort_nick time=1137563691
  adv_bubble time=1022387323
  duff_bubble time=986999012
  bubble_salem time=801146807