Rennie44/Sorting-Algorithm-Visualization

1"""2Insertion sort step-by-step for visualization.3"""4 5def insertion_sort_steps(arr):6    steps = []7    a = arr.copy()8 9    steps.append({"array": a.copy(), "compare": None, "swapped": None, "swapped_indices": None})10 11    for i in range(1, len(a)):12        key = a[i]13        j = i - 114 15        # Show initial comparison (inserting key)16        steps.append({"array": a.copy(), "compare": (i, j), "swapped": False, "swapped_indices": None})17 18        # Move elements one by one19        while j >= 0 and a[j] > key:20 21            # Swap-like shift (visualizing the movement)22            a[j + 1] = a[j]23 24            steps.append({25                "array": a.copy(),26                "compare": (j, j+1),27                "swapped": True,28                "swapped_indices": (j, j+1)29            })30 31            j -= 132 33        # Insert the key back34        a[j + 1] = key35        steps.append({36            "array": a.copy(),37            "compare": None,38            "swapped": True,39            "swapped_indices": (j+1, i)40        })41 42    steps.append({"array": a.copy(), "compare": None, "swapped": None, "swapped_indices": None})43    return steps44