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?
n^2
to be significantalgorithms
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).