sorting_iterative.py

#!python


def is_sorted(items: list[int]) -> bool:
    """Return a boolean indicating whether given items are in sorted in ascending order.
    TODO: Running time: O(n) because you must go through every item in the list in worst case
    TODO: Memory usage: O(1) because only the item variable is created, no matter how big the items list grows
    """
    # TODO: Check that all adjacent items are in order, return early if so
    for item in range(len(items) - 1):
        if items[item] > items[item + 1]:
            return False
    return True


def bubble_sort(items: list[int]) -> None:
    """Sort given items by swapping adjacent items that are out of order, and
    repeating until all items are in sorted order.
    TODO: Running time: O(n^2) because have nested for loops under worst conditions, if it's already sorted than we could exit early and have O(n)
    TODO: Memory usage: O(1), only 3 vars created, no matter how big the items list grows
    """
    # TODO: Repeat until all items are in sorted order
    for loop_count in range(len(items) - 1):
        swapped = False
        for current_index in range(len(items) - 1 - loop_count):
            # TODO: Swap adjacent items that are out of order
            if items[current_index] > items[current_index + 1]:
                items[current_index], items[current_index + 1] = (
                    items[current_index + 1],
                    items[current_index],
                )
                swapped = True
        if not swapped:
            return


def selection_sort(items: list[int]) -> None:
    """Sort given items by finding minimum item, swapping it with first
    unsorted item, and repeating until all items are in sorted order.
    TODO: Running time: O(n^2) in all cases,always searches entire unsorted portion, no early exit
    TODO: Memory usage: O(1), only 3 vars created, no matter how big the items list grows
    """
    # TODO: Repeat until all items are in sorted
    for current_position in range(len(items) - 1):
        # TODO: Find minimum item in unsorted items
        min_item_index = current_position
        for compare_item_index in range(current_position + 1, len(items)):
            if items[compare_item_index] < items[min_item_index]:
                min_item_index = compare_item_index
        # TODO: Swap it with first unsorted item
        items[current_position], items[min_item_index] = (
            items[min_item_index],
            items[current_position],
        )


def insertion_sort(items: list[int]) -> None:
    """Sort given items by taking first unsorted item, inserting it in sorted
    order in front of items, and repeating until all items are in order.
    TODO: Running time: O(n^2) worst case (reverse sorted), O(n) best case (already sorted)
    TODO: Memory usage: O(1), only creates a few variables, no matter how big the items list grows
    """
    # TODO: Repeat until all items are in sorted order
    # TODO: Take first unsorted item
    for current_position in range(1, len(items)):
        current_item = items[current_position]
        insert_position = current_position
        # TODO: Insert it in sorted order in front of items
        while insert_position > 0 and items[insert_position - 1] > current_item:
            items[insert_position] = items[insert_position - 1]
            insert_position -= 1
        items[insert_position] = current_item