3
$\begingroup$

I am in an entry-level algorithms class, and for our final project we are coding and thoroughly analyzing 6 different sorting methods. Part of the analyzation is timing the methods and comparing the runtime results depending on the original order of the array (in order to more fully grasp the concept of constant costs, I suppose). I coded the bubble sort in Java, and when I run it on an array that is in descending order, it returns a sorted array FASTER than when I run it on an array of random ints, even though it is doing, on average, twice as many swaps. It seems to me that doing twice as many operations should result in taking much longer to finish. I have NO idea what could be causing this discrepancy, and any help would be appreciated.

$\endgroup$
2
  • 2
    $\begingroup$ It may be doing more swaps but less comparisons - perhaps you need to count comparisons as well. $\endgroup$ Apr 17, 2014 at 17:57
  • 3
    $\begingroup$ Take a look at this very popular question on StackOverflow. The answer: branch prediction. $\endgroup$
    – user4577
    Apr 17, 2014 at 22:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.