По принципу нуль-единичного теста достаточно проверить все $2^{3}=8$ входов из {0,1}. Инвариант: после каждого компаратора $(i,j)$ значение на нижнем проводе $\leq$ значение на верхнем. Проверим наихудший вход $(1,0,0)$ (сверху вниз): после [$(1,2)]: min(1,0)=0$ на $1, max=1$ на $2 \to (0,1,0)$; после [$(2,3)]: (0,0,1)$; после [$(1,2)]: (0,0,1)$ уже упорядочены на $1,2; (0,0,1)$; после [$(2,3)]: (0,0,1)$. Для входа $(1,1,0)$: после [$(1,2)]: (1,1,0)\to (1,1,0)$ нет, компаратор $(1,2): min(1,1)=1, max=1\to (1,1,0)$; после [$(2,3)]: min(1,0)=0$ на $2, max=1\to (1,0,1)$; после [$(1,2)]: min(1,0)=0$ на $1\to (0,1,1)$; после [$(2,3)]: (0,1,1)$. Проверим $(1,0,1)$: после [$(1,2)]: min(1,0)=0\to (0,1,1)$; после [$(2,3)]: (0,1,1)$; после [$(1,2)]: (0,1,1)$; после [$(2,3)]: (0,1,1)$. Все 8 входов сортируются корректно. Инвариант: после $k$ компараторов число инверсий (пар $i$a$ⱼ) не возрастает и каждый компаратор устраняет хотя бы одну инверсию при её наличии.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!