More‎ > ‎

Performance Impact of Java HotSpot™ to Quick-Sort, Heap-Sort and Bubble-Sort Algorithm?

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™ optimizations.

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. 

Basics

The algorithms should show the following behavior:

 Name  Worst case performance  Best case performance  Average case performance Source
 Quick-Sort  O(n^2)  O(n log n)  O(n log n) 1 ]
 Heap-Sort  O(n log n)  O(n log n)  O(n log n) [ 2 ]
 Bubble-Sort  O(n^2)   O(n)   O(n^2) [ 3 ]

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.

Sample Code

The following Java program implements the standard Bubble-Sort, Heap-Sort and Quick-Sort algorithms without any manual optimizations. To run the program without Java HotSpot™ you need the VM option -Xint to switch off all optimizations.

// File #01: BubbleSort.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package com.sprunck.sample;

public class BubbleSort implements ISort {

    @Override
    public void sort(final int[] unsorted) {
        bubbleSort(unsorted);
    }

    private static void bubbleSort(final int[] result) {
        int length = result.length;
        boolean changed = false;
        do {
            changed = false;
            for (int i = 0; i < length - 1; i++) {
                if (result[i] > result[i + 1]) {
                    final int temp = result[i + 1];
                    result[i + 1] = result[i];
                    result[i] = temp;
                    changed = true;
                }
            }
            length -= 1;
        } while (changed && length > 1);
    }
}

// File #02: HeapSort.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package com.sprunck.sample;

import java.util.ArrayList;

public class HeapSort implements ISort {


    private ArrayList<Integer> heap;

    private int length = 0;

    @Override
    public void sort(final int[] unsorted) {

        heap = new ArrayList<Integer>(unsorted.length);
        for (final int element : unsorted) {
            insert(element);
        }

        for (int i = 0; i < unsorted.length; i++) {
            unsorted[i] = pop();
        }
    }

    private int getLeftChildIndex(final int parent) {
        return 2 * parent;
    }

    private int getRightChildIndex(final int parent) {
        return 2 * parent + 1;
    }

    private int getParentIndex(final int node) {
        return node / 2;
    }

    private Integer getValueAtIndex(final int index) {
        return heap.get(index - 1);
    }

    private void swap(int index_a, int index_b) {
        index_a--;
        index_b--;
        final Integer tmp = heap.get(index_a);
        heap.set(index_a, heap.get(index_b));
        heap.set(index_b, tmp);
    }

    private void insert(final Integer value) {
        heap.add(value);
        int current = ++length;
        int parent = getParentIndex(current);
        while (current > 1 && getValueAtIndex(current) <= getValueAtIndex(parent)) {
            swap(current, parent);
            current = parent;
            parent = getParentIndex(current);
        }
    }

    private Integer pop() {
        final Integer ret = getValueAtIndex(1);
        int current = 1;
        heap.set(0, getValueAtIndex(length));
        heap.remove(--length);
        while (getLeftChildIndex(current) <= length) {
            final int left = getLeftChildIndex(current);
            final int right = getRightChildIndex(current);
            int move = left;
            if (right <= length && getValueAtIndex(left) > getValueAtIndex(right)) {
                move = right;
            }
            if (getValueAtIndex(current) >= getValueAtIndex(move)) {
                swap(current, move);
            }
            current = move;
        }
        return ret;
    }
}

// File #03: QuickSort.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.sprunck.sample;

public class QuickSort implements ISort {
    
    @Override
    public void sort(final int[] unsorted) {
        quicksort(unsorted, 0, unsorted.length - 1);
    }

    private static void quicksort(int[] result, final int left, final int right) {
        if (left < right) {
            final int pivot_index = left + (right - left) / 2;
            final int pivot_value = result[pivot_index];
            int leftIndex = left;
            int rightIndex = right;
            while (leftIndex < rightIndex) {
                while (result[leftIndex] < pivot_value) {
                    leftIndex++;
                }
                while (result[rightIndex] > pivot_value) {
                    rightIndex--;
                }
                if (leftIndex <= rightIndex) {
                    // swap values
                    final int temp = result[leftIndex];
                    result[leftIndex] = result[rightIndex];
                    result[rightIndex] = temp;
                    leftIndex++;
                    rightIndex--;
                }
            }
            quicksort(result, left, rightIndex);
            quicksort(result, leftIndex, right);
        }
    }
}

// File #04: ISort.java

1
2
3
4
5
package com.sprunck.sample;

public interface ISort {
    public abstract void sort(int[] unsorted);
}

// File #05: SortTester.java

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package com.sprunck.sample;

import java.util.Arrays;
import java.util.Locale;

public class SortTester {
    private static final int MIN_SIZE = 500;

    private static final int MAX_SIZE = 64000;

    private static String[] ucDescriptions = { //
            "About 10% random numbers at the end of the array", //
            "About 10% random numbers at the start of the array", //
            "About 10% random numbers in the array", //
            "10 random number at the end of the array", //
            "10 random number at the start of the array", //
            "No random numbers in the array", //
            "95% random numbers in the array", //
            "Two swapped values in the array" };

    public static void main(String[] args) {

        System.out.println("QuickSort\tHeapSort\tBubbleSort\tSIZE\tRandom\tUC#\tUC\n");

        for (int uc = 0; uc <= 7; uc++) {

            for (int size = MIN_SIZE; size <= MAX_SIZE; size *= 2) {
                int randomValues = 0;
                final int[] input = new int[size];
                for (int i = 0; i < size; i++) {
                    // Use Case 0: About 10% random numbers at the end of the
                    // array
                    if (0 == uc && i < size * 0.99) {
                        input[i] = i;
                    }
                    // Use Case 1: About 10% random numbers at the start of the
                    // array
                    else if (1 == uc && i > size * 0.01) {
                        input[i] = i;
                    }
                    // Use Case 2: About 10% random numbers in the array
                    else if (2 == uc && Math.random() < 0.99d) {
                        input[i] = i;
                    }
                    // Use Case 3: 10 random number at the end of the array
                    else if (3 == uc && i < size - 10) {
                        input[i] = i;
                    }
                    // Use Case 4: 10 random number at the start of the array
                    else if (4 == uc && i > 9) {
                        input[i] = i;
                    }
                    // Use Case 5: No random numbers in the array
                    else if (5 == uc) {
                        input[i] = i;
                    }
                    // Use Case 6: 95% random numbers in the array
                    else if (6 == uc) {
                        randomValues++;
                        input[i] = (int) (Math.random() * size);
                    }
                    // Use Case 7: Two swapped values in the array
                    else if (7 == uc) {
                        if (i != size / 3) {
                            input[i] = i;
                        } else {
                            input[i] = input[i - 1];
                            input[i - 1] = i;
                            randomValues += 2;
                        }
                    } else {
                        randomValues++;
                        input[i] = (int) (Math.random() * size);
                    }
                }

                // run sort
                final int[] resultQuickSort = Arrays.copyOf(input, input.length);
                runSort(new QuickSort(), resultQuickSort);

                final int[] resultHeapSort = Arrays.copyOf(input, input.length);
                runSort(new HeapSort(), resultHeapSort);

                final int[] resultBubbleSort = Arrays.copyOf(input, input.length);
                runSort(new BubbleSort(), resultBubbleSort);

                // give the Java HotSpot the chance to optimize
                if (size > MIN_SIZE) {
                    System.out.println(size + "\t" 
                        + randomValues + "\t" 
                        + uc + "\t" + ucDescriptions[uc]);
                }

                // verify that sorting was successful
                final int[] resultExpected = Arrays.copyOf(input, input.length);
                Arrays.sort(resultExpected);
                for (int i = 0; i < size; i++) {
                    if (resultQuickSort[i] != resultExpected[i]) {
                        System.out.println(
                            "ERROR - resultQuickSort[i] != resultExpected[i], i=" + i);
                    }
                    if (resultHeapSort[i] != resultExpected[i]) {
                        System.out.println(
                            "ERROR - resultHeapSort[i] != resultExpected[i], i=" + i);
                    }
                    if (resultBubbleSort[i] != resultExpected[i]) {
                        System.out.println(
                            "ERROR - resultBubbleSort[i] != resultExpected[i], i=" + i);
                    }
                }
            }
        }
    }

    private static void runSort(ISort method, int[] input) {

        final long start = System.nanoTime();

        method.sort(input);

        final long end = System.nanoTime();
        if (input.length > MIN_SIZE) {
            System.out.print(String.format(Locale.GERMAN, "%10.3f\t", 
                    (end - start) / 1000000.0));
        }
    }

}

Expected output of SortTester.java should look like this (executed with JRE 1.7.0-b147):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 QuickSort   HeapSort BubbleSort     SIZE Random  UC#   UC

     0,063      1,215      1,992     1000     10    0 About 10% random numbers at the end of the ...
     0,147      1,076      5,519     2000     20    0 About 10% random numbers at the end of the ...
     0,241      1,806     22,109     4000     40    0 About 10% random numbers at the end of the ...
     0,488      3,988     92,009     8000     80    0 About 10% random numbers at the end of the ...
     0,978     10,068    363,192    16000    160    0 About 10% random numbers at the end of the ...
     2,094     18,401   1554,231    32000    320    0 About 10% random numbers at the end of the ...
     4,175     46,226   6106,489    64000    640    0 About 10% random numbers at the end of the ...
     0,061      0,373      0,041     1000     11    1 About 10% random numbers at the start of ... 
     0,112      0,803      0,141     2000     21    1 About 10% random numbers at the start of ...
     0,262      1,772      0,519     4000     41    1 About 10% random numbers at the start of ...
     0,473      3,846      2,136     8000     81    1 About 10% random numbers at the start of ...
     0,963      8,101      8,222    16000    161    1 About 10% random numbers at the start of ...
     2,029     19,882     33,426    32000    321    1 About 10% random numbers at the start of ...
     4,166     40,853    133,070    64000    641    1 About 10% random numbers at the start of ...
     0,051      0,350      1,408     1000     11    2 About 10% random numbers in the array
     0,104      0,797      4,704     2000     15    2 About 10% random numbers in the array
     0,237      1,678     21,470     4000     37    2 About 10% random numbers in the array
     0,488      3,739     87,753     8000     77    2 About 10% random numbers in the array
     1,028      8,258    380,041    16000    143    2 About 10% random numbers in the array
     3,054     25,234   1488,471    32000    328    2 About 10% random numbers in the array
     6,104     58,821   5823,760    64000    629    2 About 10% random numbers in the array
     0,063      0,336      1,366     1000     10    3 10 random number at the end of the array
     0,120      0,751      5,579     2000     10    3 10 random number at the end of the array
     0,226      1,838     21,332     4000     10    3 10 random number at the end of the array
     0,435      3,768     86,831     8000     10    3 10 random number at the end of the array
     0,945      8,108    345,212    16000     10    3 10 random number at the end of the array
     1,948     17,970   1406,741    32000     10    3 10 random number at the end of the array
     3,979     39,269   5658,842    64000     10    3 10 random number at the end of the array
     0,050      0,389      0,031     1000     10    4 10 random number at the start of the array
     0,109      0,766      0,068     2000     10    4 10 random number at the start of the array
     0,226      1,682      0,142     4000     10    4 10 random number at the start of the array
     0,447      4,462      0,272     8000     10    4 10 random number at the start of the array
     0,879      8,441      0,545    16000     10    4 10 random number at the start of the array
     1,760     19,348      1,082    32000     10    4 10 random number at the start of the array
     3,555     39,859      2,149    64000     10    4 10 random number at the start of the array
     0,030      0,347      0,004     1000      0    5 No random numbers in the array
     0,063      0,799      0,007     2000      0    5 No random numbers in the array
     0,131      1,682      0,012     4000      0    5 No random numbers in the array
     0,272      3,700      0,025     8000      0    5 No random numbers in the array
     0,556      9,802      0,047    16000      0    5 No random numbers in the array
     1,145     18,005      0,091    32000      0    5 No random numbers in the array
     2,424     40,502      0,181    64000      0    5 No random numbers in the array
     0,100      0,411      2,878     1000   1000    6 95% random numbers in the array
     0,208      0,905     11,508     2000   2000    6 95% random numbers in the array
     0,440      2,582     45,936     4000   4000    6 95% random numbers in the array
     0,916      4,562    184,784     8000   8000    6 95% random numbers in the array
     1,928     10,051    851,227     16000 16000    6 95% random numbers in the array
     5,836     27,738   2941,046     32000 32000    6 95% random numbers in the array
     8,577     48,511  11967,247     64000 64000    6 95% random numbers in the array
     0,030      0,337      0,007     1000      2    7 Two swapped values in the array
     0,060      0,765      0,012     2000      2    7 Two swapped values in the array
     0,128      1,712      0,023     4000      2    7 Two swapped values in the array
     0,249      3,702      0,045     8000      2    7 Two swapped values in the array
     0,527      8,118      0,090     16000     2    7 Two swapped values in the array
     1,172     17,861      0,185     32000     2    7 Two swapped values in the array
     2,334     38,445      0,380     64000     2    7 Two swapped values in the array

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. 

References

Sponsored Link