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!