Python Bubble Sort

Python Bubble Sort

Bubble Sort is the simplest sorting algorithm. It works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The algorithm gets its name because smaller elements "bubble" to the top of the list with each pass. While it's easy to understand, it is too slow for most real-world scenarios.

How Bubble Sort Works

1. Start at the beginning of the list.
2. Compare the first element with the second. If the first is greater than the second, swap them.
3. Move to the next pair of elements (the second and third) and repeat the comparison and swap if necessary.
4. Continue this process until the end of the list is reached. After the first pass, the largest element will have "bubbled" to the end.
5. Repeat the entire process for the remaining unsorted part of the list (i.e., from the beginning to the second-to-last element).
6. Continue until no swaps are needed in a full pass, which indicates the list is sorted.

Implementing Bubble Sort in Python

Here is a function that implements the bubble sort algorithm. We can add a small optimization to stop the algorithm early if the list is already sorted.

def bubble_sort(data):
    n = len(data)
    // Traverse through all array elements
    for i in range(n):
        // A flag to optimize. If no swaps in a pass, list is sorted.
        swapped = False
        // Last i elements are already in place
        for j in range(0, n-i-1):
            // traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swapped = True
        if not swapped:
            break // Exit loop if list is already sorted

// --- Usage ---
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Sorted list is:", my_list)

Time Complexity

Bubble sort has a simple but poor performance profile.

• Best Case: O(n) - If the list is already sorted and we use the swapped flag optimization, it only takes one pass to confirm.
• Worst Case: O(n²) - If the list is in reverse order, it requires n passes, with roughly n comparisons per pass.
• Average Case: O(n²)