Print all elements in sorted order from row and column wise sorted matrix - GeeksforGeeks
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of matrix in sorted order.
Example:
O(N^3)
We can use Young Tableau to solve the above problem. The idea is to consider given 2D array as Young Tableau and call extract minimum O(N)
O(N2LogN)
The idea is to use a Min Heap of size N which stores elements of first column. The do extract minimum. In extract minimum, replace the minimum element with the next element of the row from which the element is extracted.
http://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted
Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of matrix in sorted order.
Example:
Input: mat[][] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; Output: Elements of matrix in sorted order 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
O(N^3)
We can use Young Tableau to solve the above problem. The idea is to consider given 2D array as Young Tableau and call extract minimum O(N)
// A utility function to youngify a Young Tableau. This is different
// from standard youngify. It assumes that the value at mat[0][0] is
// infinite.
void
youngify(
int
mat[][N],
int
i,
int
j)
{
// Find the values at down and right sides of mat[i][j]
int
downVal = (i+1 < N)? mat[i+1][j]: INF;
int
rightVal = (j+1 < N)? mat[i][j+1]: INF;
// If mat[i][j] is the down right corner element, return
if
(downVal==INF && rightVal==INF)
return
;
// Move the smaller of two values (downVal and rightVal) to
// mat[i][j] and recur for smaller value
if
(downVal < rightVal)
{
mat[i][j] = downVal;
mat[i+1][j] = INF;
youngify(mat, i+1, j);
}
else
{
mat[i][j] = rightVal;
mat[i][j+1] = INF;
youngify(mat, i, j+1);
}
}
// A utility function to extract minimum element from Young tableau
int
extractMin(
int
mat[][N])
{
int
ret = mat[0][0];
mat[0][0] = INF;
youngify(mat, 0, 0);
return
ret;
}
// This function uses extractMin() to print elements in sorted order
void
printSorted(
int
mat[][N])
{
cout <<
"Elements of matrix in sorted order \n"
;
for
(
int
i=0; i<N*N; i++)
cout << extractMin(mat) <<
" "
;
}
The idea is to use a Min Heap of size N which stores elements of first column. The do extract minimum. In extract minimum, replace the minimum element with the next element of the row from which the element is extracted.
struct
MinHeapNode
{
int
element;
// The element to be stored
int
i;
// index of the row from which the element is taken
int
j;
// index of the next element to be picked from row
};
void
printSorted(
int
mat[][N])
{
// Create a min heap with k heap nodes. Every heap node
// has first element of an array
MinHeapNode *harr =
new
MinHeapNode[N];
for
(
int
i = 0; i < N; i++)
{
harr[i].element = mat[i][0];
// Store the first element
harr[i].i = i;
// index of row
harr[i].j = 1;
// Index of next element to be stored from row
}
MinHeap hp(harr, N);
// Create the min heap
// Now one by one get the minimum element from min
// heap and replace it with next element of its array
for
(
int
count = 0; count < N*N; count++)
{
// Get the minimum element and store it in output
MinHeapNode root = hp.getMin();
cout << root.element <<
" "
;
// Find the next elelement that will replace current
// root of heap. The next element belongs to same
// array as the current root.
if
(root.j < N)
{
root.element = mat[root.i][root.j];
root.j += 1;
}
// If root was the last element of its array
else
root.element = INT_MAX;
//INT_MAX is for infinite
// Replace root with next element of array
hp.replaceMin(root);
}
}
I don't think you can do it any faster than Ω(m n log(min(m, n)), at least not in the general case.
Suppose (without loss of generality) that m < n. Then your matrix looks like this:
Each circle is a matrix entry and each arrow indicates a known order relation (the entry at the source of the arrow is smaller than the entry at the destination of the arrow).
To sort the matrix, we must resolve all the unknown order relations, some of which are shown in the grey boxes here:
Sorting all of these boxes takes:
Read full article from Print all elements in sorted order from row and column wise sorted matrix - GeeksforGeeks2 Σk < m Ω(k log k) + (n - m + 1) Ω(m log m)= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)= Ω(m n log m)