Bubble Sort

Bubble sort works by iterating through the array repeatedly, comparing adjacent elements and swapping them if they are in the wrong order.

The algorithm keeps track of the sorted partition of the array and continues sorting the remaining unsorted partition until the entire array is sorted.

This process is repeated until one full pass is completed without any swaps being made, at this point the array is sorted.

It is named as "bubble sort" because smaller elements "bubble" to the top of the list.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Track whether any swaps were made during this pass
        swapped = False
        for j in range(0, n - i - 1):
            # Swap if the element is greater than the next
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps were made, the array is sorted
        if not swapped:
            break
    return arr
# Example usage
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = bubble_sort(data)
print("Sorted array:", sorted_data)

Pros

• Simple and easy to understand

• Because it's an in-place sorting algorithm it requires minimal additional memory space

• Works well for small lists or nearly sorted lists

Cons

• Not efficient for large lists

• Time complexity is O(n^2), which means the execution time increases rapidly with the growing size of the array

• Not suitable for real-world applications with large datasets

⚠️ Don't forget: Bubble Sort always makes one extra pass through the array!

• Even if no swaps are needed, the algorithm still completes a final comparison pass to confirm the array is sorted.
• This final "empty" pass ensures correctness, especially when optimized with a swapped flag.

✅ When answering exam questions

• Mention or account for this last pass in your explanation or trace.
• It’s a common place where students lose marks by stopping too early.

Time Complexity O(n²)

Bubble Sort has O(n²) time complexity because it uses nested loops: the outer loop runs n times, and for each pass, the inner loop compares adjacent elements up to n times. Multiplying the loops gives roughly n × n = n² comparisons. 

Space Complexity O(1)

 Bubble Sort is in-place, requiring only a constant amount of extra memory.