Trace lab in Sorting and Divide-and-Conquer

Mission

Run explicit minimum-selection passes and report the complete array after every pass.

Learning outcome: Trace selection-sort passes

Correctness contract

Invariant: A selection prefix is final; a merge emits the smallest remaining head.

Required technique: Perform explicit minimum-selection passes and append a snapshot after every completed pass.

Complexity target: time O(n^2); space O(n^2) trace output.

Input and output

Input: n followed by exactly n integers. Whitespace may be spaces or line breaks.

Output: Print each pass snapshot with single spaces inside a snapshot and the literal separator " | " between snapshots. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is positive and is followed by exactly n signed 32-bit integers.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Perform explicit minimum-selection passes and append a snapshot after every completed pass.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 5 1 4 2 3

Sample output

1 5 4 2 3 | 1 2 4 5 3 | 1 2 3 5 4 | 1 2 3 4 5

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Every pass selects the minimum of the unsorted suffix, swaps it into the next prefix position, and records the full state. Input `5 5 1 4 2 3` therefore produces `1 5 4 2 3 | 1 2 4 5 3 | 1 2 3 5 4 | 1 2 3 4 5`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.