Sorting

Bubble Sort iterates through the list, comparing adjacent elements $(lst[j], lst[j+1])$ and swapping them if they are in the wrong order ($lst[j] > lst[j+1]$). At the end of Pass 1, the largest element has "bubbled up" to the final index $n-1$. Pass 2 bubbles the second-largest element to index $n-2$, and so forth.

Optimized Bubble Sort Implementation in Python:

def bubble_sort(lst):
    n = len(lst)
    for i in range(n - 1):
        swapped = False  # Optimization flag: detects early sorted state!
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                # Swap adjacent elements:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                swapped = True
        print(f"Pass {i + 1}: {lst}")
        if not swapped:
            # If no swaps occurred in this pass, array is ALREADY SORTED!
            print("Early termination: Array sorted!")
            break
    return lst

Complexity:

• Total Comparisons (unoptimized): $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} = O(n^2)$.
• Best-case Time (Optimized): $O(n)$ when list is already sorted (terminates after Pass 1).
• Worst-case Time: $O(n^2)$ when list is in reverse sorted order.
• Space Complexity: $O(1)$ in-place auxiliary space. Stability: Stable.

Selection Sort divides the list conceptually into a sorted prefix and an unsorted suffix. In each pass $i$, it scans the entire unsorted suffix to locate the index of the minimum element, and performs exactly ONE swap to place that minimum element at index $i$:

def selection_sort(lst):
    n = len(lst)
    for i in range(n - 1):
        min_idx = i  # Assume first element of unsorted sub-list is smallest
        for j in range(i + 1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j  # Update index of smallest element found
        # Execute exactly ONE swap per pass:
        if min_idx != i:
            lst[i], lst[min_idx] = lst[min_idx], lst[i]
        print(f"Pass {i + 1}: {lst}")
    return lst

Complexity:

• Comparisons: Always strictly $\frac{n(n-1)}{2} = O(n^2)$ in ALL cases (Best, Worst, and Average)!
• Swaps: At most $n - 1$ swaps ($O(n)$ total swaps). Ideal when writing to memory is physically expensive (e.g., EEPROM flash writes).

Insertion Sort models the intuitive way a card player sorts cards in their hand. It builds a sorted sub-array from left to right. In pass $i$, it takes element $lst[i]$ (the `key`), compares it backward against elements in the sorted prefix ($j = i - 1$ down to $0$), shifts larger elements one position to the right, and drops the `key` into its correct sorted position:

def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        key = lst[i]
        j = i - 1
        # Shift elements of lst[0..i-1] that are greater than key to the right:
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key  # Insert key into correct vacancy
        print(f"Pass {i}: {lst}")
    return lst

Complexity:

• Best-case Time: $O(n)$ with $n - 1$ comparisons when the list is already sorted (while loop condition fails immediately).
• Worst-case Time: $O(n^2)$ when the list is sorted in reverse order.
• Stability: Stable. Highly efficient for small datasets ($n < 50$) or nearly-sorted data.