[Solved]: If we sort a table column-wise and then row-wise why the table is still sorted column-wise?

Problem Detail: 

Say we have a $n \times n$ table which elements are sorted column-wise, for example:

$$ \left( \begin{array}{ccc} 2 & 4 & 1 \\ 3 & 5 & 6 \\ 7 & 9 & 8 \end{array} \right) $$

I would like to prove that if we sort this table row-wise, it will be still sorted column-wise.

---

This is one of the steps to prove the shell sort correctness.

Asked By : Mateusz Piotrowski

Answered By : Yuval Filmus

Consider some column $i$ and some rows $j < k$. Let $x$ be the element at row $j$ column $i$ after the final sorting, and let $y$ be the element at row $k$ column $i$. We want to prove that $x \leq y$.

Since $x$ ended up in column $i$, there must have been $n-i$ elements in row $j$ larger than $x$. Together with $x$ itself, these are $n-i+1$ elements in row $j$ that were at least as large as $x$. The corresponding elements in row $k$ were also at least as large as $x$, since the columns were sorted. Summarizing, row $k$ contains at least $n-i+1$ elements which are at least as large as $x$. That means that after sorting, the element at position $i$ on row $k$ (that is, $y$) is at least as large as $x$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48405

3.2K people like this

 Download Related Notes/Documents