Вот простой контрпример для стабильности. Очевидно, что если ваш алгоритм сортировки строк и столбцов нестабилен, полная сортировка не имеет шансов быть стабильной, поэтому предположим, что вы выбрали стабильную подсортировку.
0 0 2 2
1 1 0 0
1 1 1' 2
2 2 2 2
Сортировка по столбцам:
0 0 0 0
1 1 1' 2
1 1 2 2
2 2 2 2
И через несколько шагов вы получите
0 0 0 0
1 1 1 1'
1 2 2 2
2 2 2 2
1' было перемещено раньше других 1 с, алгоритм не стабилен.
Корректность равна тривиально:
Можно без ограничения общности предположить, что алгоритм внутренней сортировки выглядит следующим образом:
while the list is not sorted:
select i < j such that x[i] > x[j].
swap x[i] and x[j]
Тогда весь алгоритм состоит только из таких перестановок, следовательно, поскольку существует конечный число таких i, j в начале, затем алгоритм должен завершиться.
Легко доказать, что, когда перестановок больше не происходит, весь список сортируется (сравните элементы в концы)
a < b < c < d
h > g > f > e
i < j < k < l
p > o > n > m
Поскольку вертикальные перестановки не выполняются, то в частности d < e, h < i и l < m.
Это также показывает, что вам нужно сортировать только по вертикали два крайних цв ВМН. Сортировка всех из них только улучшит производительность.
chqrl ie для ответа желтой цитаты дал мне идею для еще более простого примера счетчика:
1 0 ------> 0' 0
0' 0 columns 1 0
1 0 0 0' отсортировано по 0' 0 0 1. Это наименьший возможный встречный пример, так как все списки из 2 и 3 элементов отсортированы стабильно.