The Bubble Sort algorithm is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

Python Implementation

def bubble_sort(arr):
    """
    Sorts a list using the Bubble Sort algorithm.

    Parameters:
    arr (list): The list of elements to be sorted.

    Returns:
    list: The sorted list.
    """
    n = len(arr)
    for i in range(n):
        # Track if a swap has occurred
        swapped = False
        for j in range(0, n-i-1):
            # Compare adjacent elements
            if arr[j] > arr[j+1]:
                # Swap if they are in the wrong order
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no two elements were swapped in the inner loop, break
        if not swapped:
            break
    return arr

# Example usage
if __name__ == "__main__":
    sample_list = [64, 34, 25, 12, 22, 11, 90]
    sorted_list = bubble_sort(sample_list)
    print("Sorted list:", sorted_list)

Program Structure Explanation

• Function Definition: The function bubble_sort(arr) is defined to take a list arr as its parameter.
• Length Calculation: The length of the list is calculated using len(arr) and stored in the variable n.
• Outer Loop: The outer loop runs n times. It ensures that we pass through the list enough times to sort it.
• Swapping Flag: A boolean variable swapped is initialized to track whether any swaps were made during the inner loop.
• Inner Loop: The inner loop compares adjacent elements. If the element at index j is greater than the one at index j+1, they are swapped.
• Early Termination: If no swaps occurred during the inner loop, the list is already sorted, and the outer loop can break early.
• Return Value: The function returns the sorted list.

Example Usage

The program includes an example usage section. A sample list is provided, and the sorted result is printed to the console.