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?

Answer 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.

Answer 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.