How do you implement a basic sorting algorithm in Python?

Sorting is a fundamental operation in computer science, arranging elements of a list into an order (ascending or descending). While Python has built-in sorting functions (`list.sort()` and `sorted()`), understanding how a basic algorithm works provides valuable insight into the underlying principles. We will implement Bubble Sort, a simple comparison-based algorithm.

1. What is Sorting?

Sorting is the process of arranging a collection of items in a specific order. This order can be numerical (e.g., from smallest to largest) or lexicographical (e.g., alphabetical). Efficient sorting algorithms are crucial for many applications, including searching, database management, and data analysis.

2. Understanding Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. This pass-through is repeated until no swaps are needed, indicating that the list is sorted. The algorithm gets its name because smaller elements 'bubble' to the top (or beginning) of the list with each pass.

How it works:

• Start at the beginning of the list.
• Compare the first two elements. If the first is greater than the second, swap them.
• Move to the next pair of elements (second and third) and repeat the comparison and swap.
• Continue this process for each pair of adjacent elements until the end of the list. After this first pass, the largest element will be at the end of the list.
• Repeat the entire process for the remaining unsorted portion of the list (excluding the last element that just got sorted).
• Continue these passes until no swaps are needed during a full pass, which means the list is sorted.

3. Python Implementation of Bubble Sort

def bubble_sort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n - 1):
        # Last i elements are already in place
        # Initialize a flag to optimize: if no swaps in a pass, it's sorted
        swapped = False

        # Traverse the array from 0 to n-i-1
        # Compare adjacent elements and swap them if they are in the wrong order
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap
                swapped = True
        
        # If no two elements were swapped by inner loop, then break
        if not swapped:
            break
    return arr

4. Example Usage

my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print("Original list:", my_list) # Note: bubble_sort modifies in-place, but also returns
print("Sorted list:", sorted_list)

Output of the example: Original list: [64, 34, 25, 12, 22, 11, 90] Sorted list: [11, 12, 22, 25, 34, 64, 90]

5. Time Complexity

Bubble Sort has a time complexity of O(n^2) in the worst and average cases, where 'n' is the number of elements in the list. This makes it inefficient for large datasets compared to more advanced algorithms like Merge Sort or Quick Sort (which typically have O(n log n) complexity). However, its simplicity makes it a good choice for illustrating basic sorting principles or for very small lists that are nearly sorted.