Insertion Sort

# python
from collections import namedtuple
from collections.abc import MutableSequence

@dataclass
class InsertionOutput:
    element_count: int
    comparisons: int
    swaps: int
    elements: MutableSequence

InsertionOutput = namedtuple("InsertionOutput", ["element_count",
                                                 "comparisons",
                                                 "swaps",
                                                 "elements"])

def insertion_sort(elements: MutableSequence) -> InsertionOutput:
    """Sorts elements using iterative insertion-sort

    Args:
     elements: sortable collection of elements

    Returns:
     count of elements, comparisons made, swaps made, sorted elements
    """
    comparisons = swaps = 0
    for next_unsorted_cell in range(1, len(elements)):
        thing_to_insert = elements[next_unsorted_cell]

        in_front_of_me, to_the_right = (next_unsorted_cell - 1,
                                        next_unsorted_cell)

        while not (in_front_of_me < 0 or
                   elements[in_front_of_me] <= thing_to_insert):
            comparisons += 1
            swaps += 1
            elements[to_the_right] = elements[in_front_of_me]
            in_front_of_me, to_the_right = (in_front_of_me - 1,
                                            in_front_of_me)

        elements[to_the_right] = thing_to_insert
        swaps += 1

    return InsertionOutput(len(elements), comparisons, swaps, elements)

numba_sort = njit(insertion_sort)
things_to_sort = [numba_random.integers(low=0, high=count, size=count)
                  for count in range(1, 10**5 + 1, 1000)]

with TIMER:
    sort_output = Parallel(n_jobs=-1)(
        delayed(numba_sort)(thing_to_sort)
        for thing_to_sort in things_to_sort)

SIZE, COMPARISONS, SWAPS = 0, 1, 2
unzipped = list(zip(*sort_output))
count_frame = pandas.DataFrame({"Elements": unzipped[SIZE],
                                "Insertion": unzipped[SWAPS]})

count_frame["n^2"] = count_frame.Elements**2

melted = count_frame.melt(id_vars=["Elements"], var_name="Source", value_name="Runtime")

tooltip = [altair.Tooltip("Elements", format=","),
           altair.Tooltip("Runtime", format=","), 
           altair.Tooltip("Source:N")]

chart = altair.Chart(melted).mark_point().encode(
    x = "Elements",
    y = "Runtime",
    color="Source:N",
    tooltip=tooltip
).properties(
    width=800, height=525, title="Insertion Sort"
)

save_it(chart, "insertion-sort-comparisons")

frame = count_frame.rename(columns={"Insertion": "Random"})
del frame["n^2"]

best_things = [numpy.arange(count, dtype=int) for count in range(1, 10**5+ 1, 1000)]
worst_things = [numpy.flip(things) for things in best_things]

with TIMER:
    worst_output = Parallel(n_jobs=-1)(
        delayed(numba_sort)(thing) for thing in worst_things
)

with TIMER:
    best_output = Parallel(n_jobs=-1)(
        delayed(numba_sort)(thing) for thing in best_things
)

best_unzipped = list(zip(*best_output))
worst_unzipped = list(zip(*worst_output))

frame["Best"] = best_unzipped[SWAPS]
frame["Worst"] = worst_unzipped[SWAPS]

melted = frame.melt(id_vars=["Elements"],
                    var_name="Input",
                    value_name="Comparisons")

chart = altair.Chart(melted).mark_point().encode(
    x="Elements",
    y="Comparisons",
    color="Input",
    tooltip=[altair.Tooltip("Elements", format=","),
             altair.Tooltip("Comparisons", format=","),
             "Input"],
).properties(
    title="Insertion Sort Best, Worst, Random",
    width=800,
    height=525
).interactive()

save_it(chart, "best-worst-random")

def insertion_swaps(elements) -> dict:
    """Keeps track of the element indexes as they are swapped

    Args:
     elements: list of orderable elements

    Returns:
     dict mapping element to list of indices where it was in the elements list
    """
    swaps = {element: [index] for index, element in enumerate(elements)}

    number_of_elements = len(elements)

    for next_unsorted_cell in range(1, len(elements)):
        thing_to_insert = elements[next_unsorted_cell]

        in_front_of_me, to_the_right = (next_unsorted_cell - 1,
                                        next_unsorted_cell)

        while not (in_front_of_me < 0 or
               elements[in_front_of_me] <= thing_to_insert):
            elements[to_the_right] = elements[in_front_of_me]
            in_front_of_me, to_the_right = (in_front_of_me - 1,
                                            in_front_of_me)

        elements[to_the_right] = thing_to_insert

        for index, element in enumerate(elements):
            swaps[element].append(index)

    return swaps

inputs = random.choices(inputs, k=n)
expected = list(sorted(inputs.copy()))

output = insertion_swaps(inputs)

expect(inputs).to(contain_exactly(*expected))