Why is QuickSort so much slower than BubbleSort?

Question

I am wondering why my quickSort is so slow. It takes 10-20 seconds to sort the following array. Bubblesort (shown below) does it automatically.

public static void quickSort(int[] tab, int lowIndex, int highIndex) {
if (tab == null || tab.length == 0) {
    return;
}

int i = lowIndex;
int j = highIndex;

int pivot = tab[lowIndex + (highIndex - lowIndex) / 2];

while (i <= j) {
    while (tab[i] < pivot) {
    i++;
    }
    while (tab[j] > pivot) {
    j--;
    }

    if (i <= j) {
    int c = tab[i];
    tab[i] = tab[j];
    tab[j] = c;
    i++;
    j--;
    }

    if (lowIndex < j) {
    quickSort(tab, lowIndex, j);
    }
    if (i < highIndex) {
    quickSort(tab, i, highIndex);
    }
}

}

public static void bubbleSort(int[] arr) {
int n = arr.length - 1;
while (n >= 1) {
    for (int i = 0; i < n; i++) {
    if (arr[i] > arr[i + 1]) {
        int c = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = c;
    }
    }
    n--;
}
}

public static void main(String[] args) {
int[] t = new int[] { 5, 1, 33, 13, 21, 2, 12, 4,
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1,
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56,
    74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4,
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1,
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56,
    74, 5, 3, 74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4,
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1,
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56,
    74, 5, 3 };

Quicksort may seem slower for small data set as your implementation of quicksort contains recursion calls. — wns349, Feb 16 '13 at 13:00
The worstcase compelxity of bubblesort is n^2. The wortcase complexity of quicksort is n*ln(n). These are the worst cases, it says nothing for individual cases. How random is your data and how large? And what does 'automatically' mean? — Boris the Spider, Feb 16 '13 at 13:06
For the array in my code quicksort time is ~ 15 seconds and bubblesort less than 1 sec. — user123454321, Feb 16 '13 at 13:11
@bmorris591 The code sample seems to contain some example data. — millimoose, Feb 16 '13 at 13:13
for such a small data set 15 seconds are just too huge, there's something else that blocks. how do you invoke your sorts? — Zhedar, Feb 16 '13 at 13:15
Your `quicksort` appears to be incorrect. The recursive calls should not appear inside the `while (i <= j)` loop. There may be other problems in addition to this - you should really look at a standard implementation, millions exist via google, for instance: http://www.mycstutorials.com/articles/sorting/quicksort — Darren Engwirda, Feb 16 '13 at 13:20
You should check out this post: http://stackoverflow.com/questions/12913335/insertion-sort-vs-bubble-sort-vs-quicksort-algorithm — Andrew Martin, Feb 16 '13 at 13:45

score 1 · Accepted Answer · answered Feb 16 '13 at 21:38

Basically, your bubble sort is broken in some way - using the implementation Darren Engwirda linked to in his comment at http://www.mycstutorials.com/articles/sorting/quicksort, and running the sorts with a newly created array each time, I get the following times:

bash-3.1$ time java -cp bin Sort none

real    0m0.079s
user    0m0.000s
sys     0m0.015s
bash-3.1$ time java -cp bin Sort quick

real    0m0.084s
user    0m0.015s
sys     0m0.015s
bash-3.1$ time java -cp bin Sort bubble

real    0m0.115s
user    0m0.000s
sys     0m0.000s

where the infrastructure to run the three tests is:

private static int[] data () {
    return new int[] { ... the same data as in the OP ... };
}

public static void main(String[] args) {
    if ( args.length == 0 || args [ 0 ].equals ( "bubble" ) ) {
        for ( int i = 0; i < 1000; ++i ) {
            int[] data = data();
            bubbleSort ( data );
        }
    } else if ( args [ 0 ].equals ( "none" ) ) {
        for ( int i = 0; i < 1000; ++i ) {
            int[] data = data();
        }
    } else if ( args [ 0 ].equals ( "quick" ) ) {
        for ( int i = 0; i < 1000; ++i ) {
            int[] data = data();
            quickSort( data, 0, data.length-1 );
        }
    } else if ( args [ 0 ].equals ( "quick_op" ) ) {
        for ( int i = 0; i < 1000; ++i ) {
            int[] data = data();
            quickSort_op( data, 0, data.length-1 );
        }
    }
}

So a correctly implemented quick sort takes ~5μs to sort the data, and your bubble sort takes ~36μs to sort the data. The quick sort algorithm performs better than bubble sort for this data.

Moving the recursive call outside the loop means your code sorts the array ( though I haven't checked if there is any other flaw in it ), with the following result:

bash-3.1$ time java -cp bin Sort op_quick

real    0m0.108s
user    0m0.015s
sys     0m0.015s

Which is still faster than the bubble sort, but not as quick as the other implementation - I think you may be overlapping j and i and visiting parts of the array more than once.

Why is QuickSort so much slower than BubbleSort?

1 Answers1