Embedded Files
BY MARKUS SPRUNCK
BY MARKUS SPRUNCK
It is commonly assumed that Bubble-Sort is an extremely poor sort algorithm and gets really slow with larger number of input data. In the following a small Java implementation shows some Use Cases where Bubble-Sort can even be faster than Heap-Sort and/or Quick-Sort. One additional interesting aspect is the influence of the Java 7 HotSpot™ optimisations.
Basics
Basics
The algorithms should show the following behavior:
Figure 3 depicts the measured performance of random data and this confirms the average case performance of the three implementations.
Figure 3: measured run time depending of the number of data
Within the given data range 1000 to 64000 the fitted O(n^1.1) is a good approximation for O(n log(n)) with just some percent deviation. So, all three implementations show the expected performance for random number input.
Results
Results
In the first depiction the run time of Bubble-Sort, Heap-Sort and Quick-Sort for eight Use Cases is shown.
It demonstrates that for presorted arrays the performance of Bubble-Sort can be as good or even better than the very fast implementations of Heap-Sort and Quick-Sort.
Figure 1: Three sorting algorithms, without Java HotSpot™
Running the example program with the activated Java HotSpot™ the performance by at least a factor of ten. The performance improvements due to Java HotSpot™ are the highest for the Heap-Sort implementation. Profiling the running code from Java HotSpot™ shows that getter methods will be inlined and this saves especially for Heap-Sort a lot of overhead.
Figure 2: Three sorting algorithms, with Java HotSpot™
If just some values are unsorted in a "presorted" array, the Bubble-Sort implementation may be significantly faster than Heap-Sort and Quick-Sort.
Notice that there is a difference between the Use Case where the unsorted elements are at the beginning or at the end of the array. If you like to use Bubble-Sort, you should insert new elements at the start of the array or modify Bubble-Sort loops - the difference in performance may be huge.
Recommendations
Recommendations
For some cases Bubble-Sort is faster than Quick-Sort, e.g if you have a presorted list with just some unsorted values at the beginning of an array. If you measure the performance of an algorithm do it with and without Java HotSpot™ (VM option -Xint) . The difference can be high.
It is always a good idea to measure your time critical implementation of algorithms to get more information about the actual behavior- sometimes you get unexpected insights.
Google Sites
Report abuse