Get startedGet started for free

Bubble Sort

1. Bubble sort

Let's study some sorting algorithms.

2. Sorting algorithms

Computer science has deeply studied sorting algorithms. They solve how to sort an unsorted collection of elements in either ascending or descending order. They are important because they can reduce the complexity of problems. We will study some sorting algorithms, such as bubble sort, selection sort, insertion sort, merge sort, and quicksort.

3. Bubble sort

Let's discover bubble sort. We start comparing the first two values of the collection. If the first one is greater than the second one, as in this example,

4. Bubble sort

we swap them. Otherwise, we do nothing. Then,

5. Bubble sort

we compare the next two items. In this case, as the second value is greater than the first one, we do nothing.

6. Bubble sort

We continue doing

7. Bubble sort

the

8. Bubble sort

same

9. Bubble sort

until we reach the end of the list.

10. Bubble sort

We can see that the highest value of the list bubbled to the last position.

11. Bubble sort

We start again from the beginning

12. Bubble sort

and repeat

13. Bubble sort

the

14. Bubble sort

same steps.

15. Bubble sort

At this point, there is no need to compare the last two items because they were already sorted,

16. Bubble sort

so we start again

17. Bubble sort

and continue

18. Bubble sort

until

19. Bubble sort

all

20. Bubble sort

the values

21. Bubble sort

are

22. Bubble sort

sorted.

23. Bubble sort - implementation

Let's implement bubble sort in Python. We can do it with a nested loop. The outer loop will iterate as many times as the length of the list. On each iteration, the inner loop will iterate as many times as the length of the list minus the value of the variable i. We subtract i to avoid checking the already sorted values that are at the end of the list. In the inner loop, we will compare the adjacent elements and swap them if the first one is greater than the second one. We continue doing the same until we arrive at the end of the list. Then, we start iterating again while the i variable reaches the end. At the end of the execution, we return the sorted list. We can execute this algorithm and get the result. We can modify this code to detect if the list is already sorted and stop the execution if so.

24. Bubble sort - implementation

We can create a variable called is_sorted, initially set to False. While is_sorted is False, we will do the following. We first set the is_sorted variable to True and start iterating for all the elements in the list. If the first element is greater than the second one, we swap them and set is_sorted again to False. We continue doing the same until we arrive at the end of the list. Then, we subtract one from the list_length variable and start iterating again only if the is_sorted variable is False. If it is True, we know that the list is sorted, so we can return it.

25. Bubble sort - complexity

As we can see, the last implementation is better than the first one, but still, both have a complexity of O of n-squared. The best case of this algorithm, that is, when the list is already sorted, will also be omega of n-squared in the not improved version. However, in the improved version, it will be omega of n. Similar to Big O notation, Big omega notation is used to indicate the complexity of the best case of an algorithm. Similarly, we can study the complexity of the average case, which, expressed with Big Theta notation, is n-squared. Bubble sort doesn't perform well with highly unsorted large lists. However, with the complexity it has in its improved version, bubble sort performs well if the list is large but sorted or almost sorted. It will also perform well with small lists.

26. Let's practice!

Let's do some exercises!