Implement a sorting function using the bubble sort algorithm in Python

Write a function to sort a list of integers using a sorting algorithm of your choice e.g., bubble sort, quicksort in Python?

Certainly! Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It continues to pass through the list until no swaps are needed, indicating that the list is sorted.

Here's the implementation of bubble sort in Python:

def bubble_sort(arr):

    n = len(arr)

    # Traverse through all elements in the list

    for i in range(n):

        # Flag to optimize the algorithm by stopping if no swap occurs

        swapped = False

        # Last i elements are already in place

        for j in range(0, n-i-1):

            # Swap if the element found is greater than the next element

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

                swapped = True

        

        # If no two elements were swapped in the inner loop, then the list is sorted

        if not swapped:

            break

# Example usage:

if __name__ == '__main__':

    # Example list to be sorted

    my_list = [64, 34, 25, 12, 22, 11, 90]

    # Sorting the list using bubble sort

    bubble_sort(my_list)

    # Print the sorted list

    print("Sorted list:", my_list)

Explanation:

1. Bubble Sort Function (bubble_sort):
   • Takes a list arr as input.
   • n = len(arr) gets the length of the list.
   • Uses nested loops:
     • Outer loop (for i in range(n)) iterates through each element of the list.
     • Inner loop (for j in range(0, n-i-1)) iterates through the unsorted part of the list.
   • Compares adjacent elements (arr[j] and arr[j+1]). If arr[j] is greater than arr[j+1], swaps them.
   • Uses a swapped flag to optimize the algorithm by breaking out of the outer loop if no swaps are made in an iteration (indicating the list is already sorted).
   • Terminates early if no swaps are made in an iteration, which improves efficiency for already sorted lists.
2. Example Usage:
   • Demonstrates how to use the bubble_sort function to sort a list of integers (my_list).
   • Prints the sorted list after sorting.

Bubble sort is straightforward to implement and understand, making it suitable for educational purposes and small datasets. However, it has a worst-case time complexity of $O(n^2)$, which makes it less efficient compared to more advanced sorting algorithms like quicksort or merge sort for large datasets.