Swap Two Elements

Consider the inversion count of the permutation. Let the two values actually swapped by an operation be $x<y$. Since they are the smallest and second-smallest values in the chosen interval, every value between their positions is greater than $y$. Therefore, the total number of inversions involving these intermediate values and $x,y$ is unchanged by the swap; only the inversion relation between $x$ and $y$ changes. Thus one operation changes the total inversion count by exactly $1$, either increasing or decreasing it. Sorting must eliminate every inversion, so at least the initial number of inversions is necessary.

If the chosen interval has length two, its two elements are automatically the smallest and the second-smallest values in that interval. Thus the operation is exactly an adjacent swap. Bubble sort swaps adjacent inverted pairs one by one; every such swap decreases the inversion count by exactly one and eventually sorts the permutation.

Hence bubble sort uses the minimum possible number of operations. Its running time is $O(N^2)$, and at most $N(N-1)/2$ operations are printed. Solution written by GPT5.6