Why bubble sort is faster than quick sort

Question

I try to sort my list using two algorithms of sort: bubble and quick.
For this purpose i use algorithms module and bubble_sort , quick_sort respectively. As I know complexity of first algorithm is n^2 and second is n*log(n). But i get unexpected output from this code:

from algorithms.sorting import bubble_sort, quick_sort
import time

my_list = [1, 12, 33, 14, 52, 16, 71, 18, 94]
start1 = time.time()
for i in range(1000000):
    bubble_sort.sort(my_list)

end1 = time.time()
start2 = time.time()
for i in range(1000000):
    quick_sort.sort(my_list)

end2 = time.time()

print('Bubble sort:', end1 - start1)
print('Quick sort:',end2 - start2)

Output:

>>> Bubble sort: 7.04760217666626
>>> Quick sort: 8.181402921676636

Why in this case bubble sort is faster than quick sort?

Solution 1

The time complexity of an algorithm does not give any guarantees about the runtime; instead, it gives an estimate for asymptotic behavior of that algorithm. In your case, n = 9 very small, so the effects of hidden constants in the algorithms will become more important than the differences in the time complexities themselves.

Try rerunning your program, but this time with a much larger value of n (say n=10000). To test the general behavior of both algorithms, make sure that your input list is randomly ordered. You could also experiment with edge-case lists (i.e. already sorted) to observe the worst-case performance of quicksort and the best-case performance of bubble sort.

Solution 2

The worst case running time of quick sort is O(n^2). The worst case depends on pivot selection strategy, usually it occurs for a already sorted array (which your array is).

Also, for small data set, bubble sort or other simple sorting algorithm usually works faster than more complex algorithms. The reason is, for each iteration, simple algorithms does less calculation than complex algorithms.

For example, say bubble sort takes 3ms per iteration while quicksort takes 20ms. So for an array with 10 items.

In this case bubble sort takes 10*10*3 = 300ms.

And quicksort takes 10*log2(10)*20 = 664ms. (Considering the average case)

So bubble sort is faster here. But as we take larger dataset, quicksort becomes increasingly efficient due to lower run-time complexity.

Solution 3

Mathematically n^2 is greater than nlog(n) for all n >= 1.

So bubble sort{O(n^2)} should be slower than quick sort{O(nlog n)} for n = 9 (from example).

But the actual complexity is:

Big-O Bubble Sort: n(n-1) which is equivalent O(n^2)

Big-O Quick Sort: O(n(log n))

But as n=9 is very small, n^2 and n are comparable and the assumption n^2-n equivalent to n becomes wrong.

As for proof:

n^2-n for n=9 is 7.2

n(log n) for n=9 is 8.5 which is the same as mention in the question.

Solution 4

So what are the worst-case run-times here?

Quicksort: n^2 and Bubblesort: n^2

Remember that worst case is not always a good indicator of real world performance. In the average case,

Quicksort: nlog(n)

Bubblesort: n^2

So based on this, Quicksort is faster than Bubblesort.

However, Quicksort handles degenerate cases poorly. When the list is in almost-sorted order already, Quicksort is going to keep recursing. Bubblesort will stop as soon as its done, making Bubblesort faster in such cases.

View more solutions

Comments

[Lew Winczynski]

n^2-n for n=9 is 72, not 7.2

[user11655900]

I ran BubbleSort with 100 000 elements and it was times faster than java.utils.Array.sort in the same conditions. Though it wasn't the greatest one cause I literally copied it from GeeksForGeeks page about bubble sort(if you go there look at the second code snippet with the optimized version). I did 100 sorts with each of them and calculated their avg, each sort had a randomly generated array of ints. I know java.utils.Array.sort isn't Quicksort. So I took my implementation of QuickSort(last as pivot, shitty). It gave the same results as java.utils.Array.sort.

[shawon191]

@user11655900 The worst case running time of quick sort is O(n^2), which depends on the dataset and pivot selection. You may want to debug through your code to see why your algorithm is performing badly.

[Gabriel]

This is wrong. Quick sort is O(n^2) in the worst case, when the input is already completely sorted.