7

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?

4
  • 6
    Your test data is too small for n^2 to be significant
    – jonatan
    Oct 17, 2017 at 9:03
  • 6
    and start with a list that is not already sorted.
    – Ma0
    Oct 17, 2017 at 9:04
  • Because the list is already sorted. Quick sort might perform bad in such cases based on how the pivot elements are chosen. Oct 17, 2017 at 9:05
  • 1
    Also, your data is already sorted. I don't know that algorithms module (and you didn't say where it's from), but it looks like it's smart enough to terminate when the inner loop has performed no swaps. So in this case it's made a single pass over the list, which is O(n).
    – PM 2Ring
    Oct 17, 2017 at 9:06

7 Answers 7

8

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.

2
  • 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. May 16, 2021 at 21:53
  • @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.
    – shawon191
    Sep 13, 2021 at 9:07
7

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.

2

The reason bubble performs better than quicksort in some cases is lost to many Computer Scientists: It's true that bubble sort will result in many more "element swaps" than with quicksort. But there is more to performance than eliminating swaps. Bubblesort is generally an "in-line" routine (as opposed to a "forced" function call). Even if it's coded as a function, a good optimizing compiler will compile it in-line. And if it is not, there is still only one function call per sort. Quicksort however, relies in recursion, which forces a function call mechanism. Every time a recursion cycle occurs (a call to quicksort from within quicksort), the entire environment needs to be saved on the stack. Then a transfer of control is executed. At the end of the recursion, the entire environment needs to be restored, and another transfer of control is executed (return to the calling function). There can be a very heavy performance penalty in frequent recursions. In my humble opinion, many look at the "elegance" of quicksort and "recursion" in general, but overlook its overhead. Not saying this in a vacuum, I wrote some benchmarks and bubblesort swaps a lot more, but still beats quicksort. In those benchmarks, I found that even with data that is already "in order" quicksort will recurse N-1 times, with N being the number of elements to sort.

3
  • Quicksort without recursion would be a lot faster, right?
    – John Glen
    Apr 2, 2022 at 15:58
  • Not sure quicksort variants could be implemented without recursion - my guess is that it could not, and if it could, it would no longer be quicksort Apr 3, 2022 at 17:05
  • Update to my comment above: Results of my benchmarks show that bubble sort beats quicksort when sorting small data sets, quicksort beats bubble sort when sorting large data sets (I used 10,000 elements randomly populated) and qsort (C Library) beats both. My guess is that the qsort C library version is highly optimized, more than the default optimization if you compile quicksort yourself. Apr 3, 2022 at 18:43
1

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.

1

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.

2
  • 7
    n^2-n for n=9 is 72, not 7.2 Jun 20, 2020 at 16:42
  • This is wrong. Quick sort is O(n^2) in the worst case, when the input is already completely sorted.
    – Gabriel
    Jun 28, 2022 at 9:51
0

Firstly, try the sort on a much bigger array, so that the quadratic complexity could take precedence over the logarithmic complexity.
Note: regarding the logarithmic complexity, be careful that the log(n) as far as quicksort is concerned, is not log10, it's log2 -> O(n) should be denoted as n * lg(n)

Secondly, there is no reason to sort an already sorted array... try this:

import numpy as np
arr = np.linspace(-1e3, 1e3, 1e5)
np.random.shuffle(arr)  # Shuffling array preserving the content

If you algorithm does not accept numpy array, convert it to list:
arr_l = list(arr)

0

Notation Big O does not provide an specific runtime, but an estimation of it. Nevertheless, it is required that those estimations might variate regarding the current order of your array.

When comparing both algorithms, meaning Bubble sort and Arrays.sort, we need to consider the following:

  • Arrays.sort() runs in O(n log (n)) as best, average or performance.
  • Bubble sort, runs in:
  • List item O(n ^ 2) as worst and average case, but O(n) on its best

Therefore, the array which is being sorted, might be working on the best performance for Bubble sort, ergo will be faster

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.