# Bubble Sort

Manu

Which algorithm runs when we call `sort()` & `sorted()` methods?

Bartosz Zaczyński RP Team

@Manu Both functions use an adaptive sorting algorihm called Timsort, which was named after Tim Peters who was a major contributor to Python.

dev782

``````from timing import timed_func
``````

How to fix this error?

``````cannot import name 'timed_func'
``````

rynesmith

As an alternative to creating the decorator, you can also code in a start time and finish time. Finding the difference will reveal the total time elapsed for the function.

Below I imported the standard library’s time module and used its perf_counter function to mark the start and finish times.

``````import time
import random

def bubble_sort(items):
for i in range(len(items)):
# You minus the 1 since the number items[i] is compared with each of the others. It isn't compared to itself.
for j in range(len(items) - i - 1):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
break
return items

items = [random.randint(1, 1000) for _ in range(1000)]
start_time = time.perf_counter()
print(bubble_sort(items)[1])
finish_time = time.perf_counter()
print(finish_time - start_time)
``````

Python docs on the time module’s perf_counter function:

RealPython course on timer functions:

aquibmir

I don’t see how the `already_sorted` flag reduces time. The program still has to run the nested loop to figure out if it’s sorted or not.

And when using `@timed_func`, it seems the execution time is added as the second element of the list, hence it has to be printed out with `print(bubble_sort(items)[1])` . Correct?

Bartosz Zaczyński RP Team

@aquibmir With the `already_sorted` flag, you stop the outer loop as soon as the inner loop determines that the elements are sorted. Consider a list of numbers that are already in the expected order:

``````bubble_sort([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
``````

In that case, you’ll loop over all elements exactly once, concluding there’s no need to sort them anymore because you haven’t swapped any of the element pairs during the iteration. Otherwise, if you didn’t have that flag, then the outer loop would run ten times for all ten elements in your sequence of items.

to join the conversation.