Animating Algorithms in SwiftUI: A Step-Recorder Pattern for Visualising Sorts, Searches and Graphs

// Don't do this.
func bubbleSortAnimated() async {
    for i in 0..<values.count {
        for j in 0..<values.count - i - 1 {
            highlighted = [j, j + 1]
            try? await Task.sleep(for: .milliseconds(300))
            if values[j] > values[j + 1] { values.swapAt(j, j + 1) }
        }
    }
}

struct Bar: Identifiable, Hashable {
    let id: Int // stable identity, so SwiftUI can animate moves
    let value: Int
}

struct ArrayStep: Hashable {
    enum Action: Hashable { case compare, swap, overwrite, markSorted, done }

    var bars: [Bar]
    var action: Action
    var active: Set<Int> = [] // indices being looked at
    var sorted: Set<Int> = [] // indices known to be final
    var caption: String
}

struct StepRecorder {
    private(set) var steps: [ArrayStep] = []
    var bars: [Bar]
    var sorted: Set<Int> = []

    init(_ values: [Int]) {
        bars = values.enumerated().map { Bar(id: $0.offset, value: $0.element) }
        record(.compare, [], "Start with \(values.count) unsorted values.")
    }

    mutating func record(_ action: ArrayStep.Action, _ active: Set<Int>, _ caption: String) {
        steps.append(ArrayStep(bars: bars, action: action,
                               active: active, sorted: sorted, caption: caption))
    }
}

func insertionSortSteps(_ input: [Int]) -> [ArrayStep] {
    var r = StepRecorder(input)
    guard r.bars.count > 1 else { return r.steps }

    for i in 1..<r.bars.count {
        var j = i
        r.record(.compare, [j], "Take \(r.bars[j].value) and insert it into the sorted left part.")
        while j > 0 {
            r.record(.compare, [j - 1, j], "Compare \(r.bars[j - 1].value) and \(r.bars[j].value).")
            guard r.bars[j - 1].value > r.bars[j].value else { break }
            r.bars.swapAt(j - 1, j)
            r.record(.swap, [j - 1, j], "\(r.bars[j].value) is larger, so shift it right.")
            j -= 1
        }
    }
    r.sorted = Set(r.bars.indices)
    r.record(.done, [], "Sorted.")
    return r.steps
}

import XCTest

final class InsertionSortStepTests: XCTestCase {
    func testFinalStepIsSorted() {
        let steps = insertionSortSteps([5, 2, 4, 6, 1, 3])
        XCTAssertEqual(steps.last?.bars.map(\.value), [1, 2, 3, 4, 5, 6])
        XCTAssertEqual(steps.last?.action, .done)
    }
}

import SwiftUI

@MainActor
final class StepPlayer<Step>: ObservableObject {
    @Published private(set) var index = 0
    @Published var isPlaying = false
    @Published var speed: Double = 1.0 // 0.5x, 1x, 2x …

    let steps: [Step]
    var baseInterval: Duration = .milliseconds(600)
    private var playTask: Task<Void, Never>?

    init(steps: [Step]) { self.steps = steps }

    var current: Step { steps[index] }
    var isAtEnd: Bool { index == steps.count - 1 }

    func play() {
        guard !isPlaying else { return }
        if isAtEnd { index = 0 } // "replay"
        isPlaying = true
        playTask = Task { [weak self] in
            while let self, self.isPlaying, !self.isAtEnd {
                try? await Task.sleep(for: self.baseInterval / self.speed)
                guard !Task.isCancelled, self.isPlaying else { return }
                self.index += 1
            }
            self?.isPlaying = false
        }
    }

    func pause() {
        isPlaying = false
        playTask?.cancel()
    }

    func step(by delta: Int) {
        pause()
        index = min(max(index + delta, 0), steps.count - 1)
    }

    func seek(to newIndex: Int) {
        pause()
        index = min(max(newIndex, 0), steps.count - 1)
    }
}

struct ArrayStepView: View {
    @ObservedObject var player: StepPlayer<ArrayStep>

    var body: some View {
        let step = player.current
        let maxValue = max(step.bars.map(\.value).max() ?? 1, 1)

        VStack(spacing: 16) {
            HStack(alignment: .bottom, spacing: 6) {
                ForEach(Array(step.bars.enumerated()), id: \.element.id) { index, bar in
                    VStack(spacing: 4) {
                        RoundedRectangle(cornerRadius: 4)
                            .fill(color(for: index, in: step))
                            .frame(height: CGFloat(bar.value) / CGFloat(maxValue) * 180)
                        Text("\(bar.value)").font(.caption2.monospacedDigit())
                    }
                }
            }
            .frame(height: 210)
            .animation(.spring(duration: 0.35), value: player.index)

            Text(step.caption)
                .font(.callout)
                .multilineTextAlignment(.center)
                .frame(minHeight: 44)

            HStack(spacing: 24) {
                Button { player.step(by: -1) } label: { Image(systemName: "backward.frame.fill") }
                Button { player.isPlaying ? player.pause() : player.play() } label: {
                    Image(systemName: player.isPlaying ? "pause.fill" : "play.fill")
                }
                Button { player.step(by: 1) } label: { Image(systemName: "forward.frame.fill") }
                Picker("Speed", selection: $player.speed) {
                    Text("0.5×").tag(0.5); Text("1×").tag(1.0); Text("2×").tag(2.0)
                }
                .pickerStyle(.segmented).frame(width: 150)
            }
            .font(.title2)
        }
        .padding()
    }

    private func color(for index: Int, in step: ArrayStep) -> Color {
        if step.sorted.contains(index) { return .green }
        if step.active.contains(index) { return step.action == .swap ? .orange : .yellow }
        return .blue.opacity(0.6)
    }
}

struct SearchStep: Hashable {
    var low: Int, high: Int, mid: Int?
    var found: Int?
    var caption: String
}

func binarySearchSteps(_ sorted: [Int], target: Int) -> [SearchStep] {
    var steps: [SearchStep] = []
    var low = 0, high = sorted.count - 1
    while low <= high {
        let mid = low + (high - low) / 2
        steps.append(.init(low: low, high: high, mid: mid, found: nil,
                           caption: "Check the middle: \(sorted[mid])."))
        if sorted[mid] == target {
            steps.append(.init(low: low, high: high, mid: mid, found: mid,
                               caption: "Found \(target) at index \(mid)."))
            return steps
        }
        if sorted[mid] < target {
            low = mid + 1
            steps.append(.init(low: low, high: high, mid: nil, found: nil,
                               caption: "\(sorted[mid]) < \(target): discard the left half."))
        } else {
            high = mid - 1
            steps.append(.init(low: low, high: high, mid: nil, found: nil,
                               caption: "\(sorted[mid]) > \(target): discard the right half."))
        }
    }
    steps.append(.init(low: low, high: high, mid: nil, found: nil,
                       caption: "The window is empty: \(target) isn't in the array."))
    return steps
}

struct GraphStep: Hashable {
    var visited: Set<Int>
    var frontier: [Int] // the queue
    var current: Int?
    var caption: String
}

func bfsSteps(adjacency: [Int: [Int]], start: Int) -> [GraphStep] {
    var steps: [GraphStep] = []
    var visited: Set<Int> = [start]
    var queue = [start]
    steps.append(.init(visited: visited, frontier: queue, current: nil,
                       caption: "Start at \(start)."))

    while !queue.isEmpty {
        let node = queue.removeFirst()
        steps.append(.init(visited: visited, frontier: queue, current: node,
                           caption: "Visit \(node)."))
        for next in adjacency[node, default: []] where !visited.contains(next) {
            visited.insert(next)
            queue.append(next)
            steps.append(.init(visited: visited, frontier: queue, current: node,
                               caption: "Discover \(next); add it to the queue."))
        }
    }
    steps.append(.init(visited: visited, frontier: [], current: nil, caption: "Done."))
    return steps
}

import Charts

struct ComplexityPoint: Identifiable {
    let id = UUID()
    let n: Int
    let ops: Double
    let label: String
}

struct ComplexityChart: View {
    private var points: [ComplexityPoint] {
        stride(from: 1, through: 64, by: 3).flatMap { n -> [ComplexityPoint] in
            let x = Double(n)
            return [
                .init(n: n, ops: log2(x), label: "O(log n)"),
                .init(n: n, ops: x, label: "O(n)"),
                .init(n: n, ops: x * log2(max(x, 2)), label: "O(n log n)"),
                .init(n: n, ops: x * x, label: "O(n²)")
            ]
        }
    }

    var body: some View {
        Chart(points) { p in
            LineMark(x: .value("n", p.n), y: .value("Operations", p.ops))
                .foregroundStyle(by: .value("Complexity", p.label))
        }
        .chartYScale(domain: 0...600) // clip n², or it flattens everything else
        .frame(height: 240)
    }
}

.onChange(of: player.index) { _ in
    UIAccessibility.post(notification: .announcement, argument: player.current.caption)
}