Sort with bubble sort

Here is how to sort a list from smallest to largest. While it is often better to use a pre-existing function in practice, understanding the basics of sorting algorithms is beneficial. This knowledge helps you choose the most appropriate algorithm for your needs.

Sorting algorithms are generally evaluated based on two criteria:

• ⏱️ Speed: The time they take to execute.
• 🧠 Memory: The memory they consume.

A crucial concept in evaluating algorithms is the Big O Notation, which describes how algorithms behave (in terms of speed and memory) as the input size increases. Here are some examples to illustrate this:

• 🥇 O(1): The execution time remains constant regardless of input size.
• 🥈 O(log n): The execution time grows slowly, following a logarithmic pattern.
• 🥉 O(n): The execution time grows linearly with input size.
• 🥲 O(n^2): The execution time grows quadratically, which can become significant with larger inputs.

Consider an algorithm that:

• ⌛ Takes 1 second to execute.
• ➡️ For an input size of 10.

If we double the input size from 10 to 20, the execution time will increase differently depending on the algorithm’s Big O notation:

• If O(1), the time remains 1 second.
• If O(log n), the time increases to approximately 1.3 seconds.
• If O(n), the time doubles to 2 seconds.
• If O(n^2), the time quadruples to 4 seconds, indicating a significant increase.

Understanding the Big O notation is essential for selecting the right algorithm. With that in mind, we will implement a sorting algorithm known as bubble sort. This algorithm is simple to implement and has a worst-case time complexity of O(n^2). While not the most efficient, it is straightforward and educational. Its operation is as follows:

• ⚖️ Compare each element with the next one.
• ➡️ If the current element is greater, swap it with the next one.
• 🔄 In each new iteration, reduce the number of elements to iterate over, as the largest elements are sorted towards the end.
• 📊 After all iterations, the list l is sorted.

def bubble_sort(l):
    n = len(l)
    for i in range(n):
        for j in range(0, n-i-1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
                # Hint: Can be optimized
    return l

We can use this function as follows:

l = [64, 34, 25, 12, 22, 11, 90]
l_sorted = bubble_sort(l)
print("Sorted:", l_sorted)
# Sorted: [11, 12, 22, 25, 34, 64, 90]

✏️ Exercises:

• In the bubble_sort function, we have left a hint. This algorithm can be optimized in a straightforward way to avoid redundant work. You can achieve this in two lines of code. Optimize it and explain your changes.
• Modify the bubble_sort function to sort the list l from highest to lowest.