Why bubble sort is faster than quick sort

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.

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.

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

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.