Re: [algogeeks] Re: sort 2D array
@all I have come across this question earlier. it's a young's tableaus ( cormen pg. 167 ) can be treated as min heap. solution can be found in mit online study material. i'll post the link here as soon as i remember it. On 1/24/12, atul anand atul.87fri...@gmail.com wrote: @praveen : k way merge would require extra space right??question is to do it in place. On Tue, Jan 24, 2012 at 5:47 PM, praveen raj praveen0...@gmail.com wrote: This can be done... k way merge... c- number of columns r- number of rows In O(c*r*log(r)) PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
This can be done... k way merge... c- number of columns r- number of rows In O(c*r*log(r)) PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@praveen : k way merge would require extra space right??question is to do it in place. On Tue, Jan 24, 2012 at 5:47 PM, praveen raj praveen0...@gmail.com wrote: This can be done... k way merge... c- number of columns r- number of rows In O(c*r*log(r)) PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@lucifer:nice explanation !... just to make a small clarification, in your stabilisation part u jus compare x with min (b,d) , make a swap if necessary and then next time u compare it shud be =min(b,d) and so u break. x b c d e f g h i so now after breaking x is less than both b and d but present b could be greater than e right? for example initally it cud be 8 5 6 7. . . . and we swap 8 and 5now 8 is above 7 after swap ...but is this taken care of next iteration when we do swaps of a[row][col] with a[row+1][0]?? so is heapify sep in all just comparison of x with b and d only and swap if needed?? On Sat, Jan 14, 2012 at 1:48 AM, Gaurav Kalra gvka...@gmail.com wrote: Bases on algorithm suggested by Lucifer, I have coded the problem in C (please see attachment). The code has been tested against the following test cases: 1 3 4 8 9 2 5 18 25 50 6 7 22 45 55 and 1 2 7 3 5 8 4 6 9 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kQ0gKL_2h7oJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@lucifer: yes I get that...I was just saying that after a swap has happened
within the while loop ( since x min(b,d) might have been the case ) ,
then in the next looping within while, break wud happen right? meaning it
doesnt stay in the while after a swap happens...
On Sun, Jan 22, 2012 at 3:25 PM, Lucifer sourabhd2...@gmail.com wrote:
@Arun
If you read the post in which i have explained the process properly,
the following is also present:
while(1)
{
If x = min (b,d ),
/* here b is nothing but the element placed next to 'x' on the same
row..
d is the element placed right below 'x' in the same column...
then we are done...*/
break;
else
swap ('x', min (b,d))
}
If you see in the comments i have mentioned that b and d are not
exactly the same b and d as shown in the matrix.. but they are current
right and current bottom elements of 'x'..
Hence, the swaps go on till the condition x = min (b,d ) is not
satisfied..
On Jan 23, 3:44 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer:nice explanation !... just to make a small clarification, in
your
stabilisation part u jus compare x with min (b,d) , make a swap if
necessary and then next time u compare it shud be =min(b,d) and so u
break.
x b c
d e f
g h i
so now after breaking x is less than both b and d but present b could be
greater than e right? for example initally it cud be
8 5
6 7.
.
.
.
and we swap 8 and 5now 8 is above 7 after swap ...but is this taken
care of next iteration when we do swaps of a[row][col] with a[row+1][0]??
so is heapify sep in all just comparison of x with b and d only and swap
if
needed??
On Sat, Jan 14, 2012 at 1:48 AM, Gaurav Kalra gvka...@gmail.com wrote:
Bases on algorithm suggested by Lucifer, I have coded the problem in C
(please see attachment).
The code has been tested against the following test cases:
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
and
1 2 7
3 5 8
4 6 9
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/kQ0gKL_2h7oJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does
bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@ lucifer: thank you !
On Sun, Jan 22, 2012 at 4:12 PM, Lucifer sourabhd2...@gmail.com wrote:
@Arun,
Nope.. the loop exits only when there are no more swaps possible...
Let me explain with an example..
x b c
d e f
g h i
say x min(b,d) , where min(b,d) = b,
Hence, swap happens..
b x c
d e f
g h i
say, x min(c, e), where min(c,e) = e..
Hence, swap takes place..
b e c
d x f
g h i
Now say,
x = min(f,h)..
Hence, we hit the break statement and exit from the loop..
On Jan 23, 5:03 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer: yes I get that...I was just saying that after a swap has
happened
within the while loop ( since x min(b,d) might have been the case ) ,
then in the next looping within while, break wud happen right? meaning
it
doesnt stay in the while after a swap happens...
On Sun, Jan 22, 2012 at 3:25 PM, Lucifer sourabhd2...@gmail.com wrote:
@Arun
If you read the post in which i have explained the process properly,
the following is also present:
while(1)
{
If x = min (b,d ),
/* here b is nothing but the element placed next to 'x' on the same
row..
d is the element placed right below 'x' in the same column...
then we are done...*/
break;
else
swap ('x', min (b,d))
}
If you see in the comments i have mentioned that b and d are not
exactly the same b and d as shown in the matrix.. but they are current
right and current bottom elements of 'x'..
Hence, the swaps go on till the condition x = min (b,d ) is not
satisfied..
On Jan 23, 3:44 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer:nice explanation !... just to make a small clarification, in
your
stabilisation part u jus compare x with min (b,d) , make a swap if
necessary and then next time u compare it shud be =min(b,d) and so u
break.
x b c
d e f
g h i
so now after breaking x is less than both b and d but present b
could be
greater than e right? for example initally it cud be
8 5
6 7.
.
.
.
and we swap 8 and 5now 8 is above 7 after swap ...but is this
taken
care of next iteration when we do swaps of a[row][col] with
a[row+1][0]??
so is heapify sep in all just comparison of x with b and d only and
swap
if
needed??
On Sat, Jan 14, 2012 at 1:48 AM, Gaurav Kalra gvka...@gmail.com
wrote:
Bases on algorithm suggested by Lucifer, I have coded the problem
in C
(please see attachment).
The code has been tested against the following test cases:
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
and
1 2 7
3 5 8
4 6 9
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/kQ0gKL_2h7oJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does
bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does
bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@prakash...ya i realized that and it will be sorted row and column wise.which will become same as forming min-heapand my algo will become same what lucifer had already specified... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@ all k-way people : I dont get it how the complexity would be O(m*n) . I just went through the algo and I feel that one would need to find the minimum element among the head-elements of all individual row-arrays, for all the resulting m*n elements. I say so since we may not necessarily have a sorted column-array(array formed by taking the head elements of each row-array) each time we look for the min element. Please correct me if I am wrong. @Lucifer- yeah we need to only traverse the columns till the current column. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
any idea on how to merge two sorted arrays of size m and size n in O(m+n) time and without extra space ? On Wed, Jan 11, 2012 at 3:22 PM, Dipit Grover dipitgro...@gmail.com wrote: @ all k-way people : I dont get it how the complexity would be O(m*n) . I just went through the algo and I feel that one would need to find the minimum element among the head-elements of all individual row-arrays, for all the resulting m*n elements. I say so since we may not necessarily have a sorted column-array(array formed by taking the head elements of each row-array) each time we look for the min element. Please correct me if I am wrong. @Lucifer- yeah we need to only traverse the columns till the current column. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@shady : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514rep=rep1type=pdf it is not easy to merge sorted array inplace. check this link..hope this help. On Wed, Jan 11, 2012 at 4:53 PM, shady sinv...@gmail.com wrote: any idea on how to merge two sorted arrays of size m and size n in O(m+n) time and without extra space ? On Wed, Jan 11, 2012 at 3:22 PM, Dipit Grover dipitgro...@gmail.comwrote: @ all k-way people : I dont get it how the complexity would be O(m*n) . I just went through the algo and I feel that one would need to find the minimum element among the head-elements of all individual row-arrays, for all the resulting m*n elements. I say so since we may not necessarily have a sorted column-array(array formed by taking the head elements of each row-array) each time we look for the min element. Please correct me if I am wrong. @Lucifer- yeah we need to only traverse the columns till the current column. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
i have little doubt in complexity of proposed algo..
aren't we including complexity of heapifying each time. ??
On Wed, Jan 11, 2012 at 2:57 PM, Lucifer sourabhd2...@gmail.com wrote:
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M} { N*(M+N-i) }
= M * N * (M + 2N - 1) /2
On Jan 11, 2:19 pm, Dipit Grover dipitgro...@gmail.com wrote:
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : sum over all i (1 to M} {
i*(M+N-i)} .
Shouldnt it be M * sum over all i(1 to N) {(M+N-i)} ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of the next row for each element of the current row.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@Lucifer
I am not getting how u r working with heapifying each time ..
Initially the array is such that minimum value is ay (0,0) and and max at
index (m-1,n-1)
Now when u swap a value
Then u heapify i.e. make the prior arrangement again but that in turn will
lead to few swaps and so on...(Recursive)
Do you think it will be possible this way ?
Please correct me in case I got things wrong here
regards
Ankur
On Wed, Jan 11, 2012 at 5:07 PM, atul anand atul.87fri...@gmail.com wrote:
i have little doubt in complexity of proposed algo..
aren't we including complexity of heapifying each time. ??
On Wed, Jan 11, 2012 at 2:57 PM, Lucifer sourabhd2...@gmail.com wrote:
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M} { N*(M+N-i) }
= M * N * (M + 2N - 1) /2
On Jan 11, 2:19 pm, Dipit Grover dipitgro...@gmail.com wrote:
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : sum over all i (1 to M} {
i*(M+N-i)} .
Shouldnt it be M * sum over all i(1 to N) {(M+N-i)} ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of the next row for each element of the current row.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@Shady : you would definitely need two index variables for each array I feel. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
sorry I mean 1 variable per each array -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@Lucifier : it seem that the sub-matrix need to be heapifyed for A[i][j] is A[i+1][j] to A[row][col] there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you have mentioned above. for eg :- 1 3 4 8 9 // 3 2 , so swap and heapify 2 5 18 25 50 6 7 22 45 55 we get, 1 2 4 8 9 3 5 18 25 50 6 7 22 45 55 replace it with 4 ( 4 3) we get, 1 2 3 8 9 4 5 18 25 50 6 7 22 45 55 now after heapify this highlighted array we will get 4 as a min value , replace it with 8 ( 8 4) we get 1 2 3 4 9 8 5 18 25 50 6 7 22 45 55 after heapifying we get, 1 2 3 4 9 5 8 18 25 50 6 7 22 45 55 here 9 5 replace it. we, get 1 2 3 4 5 9 8 18 25 50 6 7 22 45 55 after heapify we get, 1 2 3 4 5 6 8 18 25 50 9 7 22 45 55 as we can see , 1st row is not included in the heapify procedure. correct me if i am wrong. On Wed, Jan 11, 2012 at 5:27 PM, Lucifer sourabhd2...@gmail.com wrote: @Ankur.. Yes... If you follow the algo that i have presented above and use Atul's example you will be able to figure out.. Maybe, the confusion is regarding heapfying.. ryt?? I am assuming so.. Now as i said a submatrix rooted at A[i , j] is nothing but a heap where its subtrees share a few nodes... Now, the first thing is to visualize the heap... For a heap in the form of submatrix rooted at A[i][j], its children are subtrees in the form of submatrix rooted at A[i+][j] and A[i][j +1]... Now, imagine that you apply the normal heap-stabilizing approach when the root element of a heap is being replaced by some other value... Do it for an example submatrix (identified as explained above and also whose rows and columns are sorted) and you will see how it works... On Jan 11, 4:44 pm, Dipit Grover dipitgro...@gmail.com wrote: @Shady : you would definitely need two index variables for each array I feel. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
abt complexity. now considering worst case scenario where swapping take place every time. now assuming that we heapifying procedure , considering rows from i+1 to M as M-(i+1) 1-dimensional array . now heapify will take O(log(m*n)) time so complexity would be M*N*log(M*N)) please correct me if i am doing wrong analysis. and about the algorithm , i have little doubt if last row after completing this procedure will remain sorted or not. On Wed, Jan 11, 2012 at 9:42 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifier : it seem that the sub-matrix need to be heapifyed for A[i][j] is A[i+1][j] to A[row][col] there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you have mentioned above. for eg :- 1 3 4 8 9 // 3 2 , so swap and heapify 2 5 18 25 50 6 7 22 45 55 we get, 1 2 4 8 9 3 5 18 25 50 6 7 22 45 55 replace it with 4 ( 4 3) we get, 1 2 3 8 9 4 5 18 25 50 6 7 22 45 55 now after heapify this highlighted array we will get 4 as a min value , replace it with 8 ( 8 4) we get 1 2 3 4 9 8 5 18 25 50 6 7 22 45 55 after heapifying we get, 1 2 3 4 9 5 8 18 25 50 6 7 22 45 55 here 9 5 replace it. we, get 1 2 3 4 5 9 8 18 25 50 6 7 22 45 55 after heapify we get, 1 2 3 4 5 6 8 18 25 50 9 7 22 45 55 as we can see , 1st row is not included in the heapify procedure. correct me if i am wrong. On Wed, Jan 11, 2012 at 5:27 PM, Lucifer sourabhd2...@gmail.com wrote: @Ankur.. Yes... If you follow the algo that i have presented above and use Atul's example you will be able to figure out.. Maybe, the confusion is regarding heapfying.. ryt?? I am assuming so.. Now as i said a submatrix rooted at A[i , j] is nothing but a heap where its subtrees share a few nodes... Now, the first thing is to visualize the heap... For a heap in the form of submatrix rooted at A[i][j], its children are subtrees in the form of submatrix rooted at A[i+][j] and A[i][j +1]... Now, imagine that you apply the normal heap-stabilizing approach when the root element of a heap is being replaced by some other value... Do it for an example submatrix (identified as explained above and also whose rows and columns are sorted) and you will see how it works... On Jan 11, 4:44 pm, Dipit Grover dipitgro...@gmail.com wrote: @Shady : you would definitely need two index variables for each array I feel. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
@Lucifier : yes i didnt hepified properly in my previous post intentionally. i only purpose was to set min at position A[i+1][j] after heafiying.( rest i dint care ) . secondly about the complexity, what i was saying if given array is:- 1 3 4 8 9 2 5 18 25 50 6 7 22 45 55 now comparing 3 2 , swap we get 1 2 4 8 9 3 5 18 25 50 6 7 22 45 55 now about heapifying the highlighted array , i was considering this highlighted matrix 3 5 18 25 50 6 7 22 45 55 as two 1-dimensional array 3 5 18 25 50 6 7 22 45 55 now we can apply heapify procedure to this 1-D array (bcozz in m/m this 2D array is nothing but contiguous acquired space ) PARENT = floor(*i*/2) LEFT (*i*) = 2i RIGHT (*i*) = 2i + 1 is this approach is wrong ?? On Wed, Jan 11, 2012 at 10:34 PM, Lucifer sourabhd2...@gmail.com wrote: @atul.. Sorry, but i don't agree with both of ur posts... First of all, the complexity won't be log(m*n) for heapifying.. log(m*n) is valid in case of a heap represented in the form of a binary tree.. But, i have have repeatedly stressing in my previous posts that the submatrix heap is not a binary tree heap but rather a graph or say a binary tree (not really tree) where its subtrees share some nodes... Disagree with the following comment.. /** it seem that the sub-matrix need to be heapifyed for A[i][j] is A[i+1][j] to A[row][col] there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you have mentioned above. **/ Also, i see that you have not properly heapified the submatrices correctly in the example that u have provided in the previous post.. Plz go thru my last post and see if ur doubts can get clarified.. - Really sorry, in case previously given details by me were inadequate... Was posting in a hurry :)... Hope, now all doubts would be cleared... --- On Jan 11, 9:55 pm, Lucifer sourabhd2...@gmail.com wrote: @Ankur.. I will try to explain the approach with an example.. Say the given matrix (sorted row wise and column wise) is as follows: a1 a2a3 a4 b1 b2b3 b4 c1 c2c3 c4 d1 d2d3 d4 Now, we want to sort the 2D array such that when all the rows are aligned sequentially it should result in a sorted sequence.. i.e. F1F2F3F4 . F13 F14 F15 F16 such that F1 = F2 == F16.. Now, let take each row at a time and ensure that that row contains all the elements as expected in the output matrix.. Row - 1 : M[0][0] = a1, which is at the correct place.. hence we won't touch it.. Now our task is to pick the second smallest no. in the matrix and place it at M[0][1].. Currently, M[0][1] is the second smallest in Row-1, but we are not sure whether its the second smallest in the entire matrix.. Hence, only way we can check that is to look in the submatrix (M[1][0] -- M[3][3]) Now, as we know that in the submatrix enclosed within (M[1][0] -- M[3] [3]) the smallest element present in this submatrix is positioned at M[1][0], therefore we will check M[0][1] against M[1][0].. If M[0][1] = M[1][0], that means M[0][1] has the second smallest element in the entire matrix.. else M[1][0] is the second smallest element in the entire matrix and we will swap M[1][0] with M[0][1].. Now, there are few things we need ensure if we end up swapping the values: 1) After swapping M[0][1]'s new value will be smaller than its original value, therefore the following is still valid: M[0][1] = M[0][2] =M[0][3] and also as M[0][1]'s new value was previously placed below M[0][0], hence it is = M[0][0] .. that means after swapping Row-1 still mains the sorted order... 2) Old value of M[1][0] = M[1][1].. Hence, the new value of M[0][1] is still = M[1][1].. therefore the sorted order of Column-2 is still valid... 3) Now, new value of M[1][0] = M[0][0] as an impact of old value of M[0][1] = M[0][0] Also, new value of M[1][0] = M[1][1] as an impact of old value of M[0][1] = M[1][1].. [ point 3 can be proved by the using the explanation from points 1 2.. 4) Now the only thing that we need to ensure is that Column - 1 is in sorted order i.e M[1][0] (new) = M[2][0] (old).. If the above is true that means the submatrix enclosed within (M[1][0] -- M[3][3]) is stabalized and has the row/column wise sorted order property in place... What if its not ?? then we need to readjust the submatrix ... Once we do that we are done for the current iteration.. [ we will talk abt stabalization in sometime.. lets take it for granted right now..] Now, we will follow the same approach for M[0][2], so that it holds the third largest element.. Once we are done with
Re: [algogeeks] Re: sort 2D array
correction : /*set min at position A[i+1][0] after heafiying */ On Wed, Jan 11, 2012 at 11:07 PM, atul anand atul.87fri...@gmail.comwrote: @Lucifier : yes i didnt hepified properly in my previous post intentionally. i only purpose was to set min at position A[i+1][j] after heafiying.( rest i dint care ) . secondly about the complexity, what i was saying if given array is:- 1 3 4 8 9 2 5 18 25 50 6 7 22 45 55 now comparing 3 2 , swap we get 1 2 4 8 9 3 5 18 25 50 6 7 22 45 55 now about heapifying the highlighted array , i was considering this highlighted matrix 3 5 18 25 50 6 7 22 45 55 as two 1-dimensional array 3 5 18 25 50 6 7 22 45 55 now we can apply heapify procedure to this 1-D array (bcozz in m/m this 2D array is nothing but contiguous acquired space ) PARENT = floor(*i*/2) LEFT (*i*) = 2i RIGHT (*i*) = 2i + 1 is this approach is wrong ?? On Wed, Jan 11, 2012 at 10:34 PM, Lucifer sourabhd2...@gmail.com wrote: @atul.. Sorry, but i don't agree with both of ur posts... First of all, the complexity won't be log(m*n) for heapifying.. log(m*n) is valid in case of a heap represented in the form of a binary tree.. But, i have have repeatedly stressing in my previous posts that the submatrix heap is not a binary tree heap but rather a graph or say a binary tree (not really tree) where its subtrees share some nodes... Disagree with the following comment.. /** it seem that the sub-matrix need to be heapifyed for A[i][j] is A[i+1][j] to A[row][col] there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you have mentioned above. **/ Also, i see that you have not properly heapified the submatrices correctly in the example that u have provided in the previous post.. Plz go thru my last post and see if ur doubts can get clarified.. - Really sorry, in case previously given details by me were inadequate... Was posting in a hurry :)... Hope, now all doubts would be cleared... --- On Jan 11, 9:55 pm, Lucifer sourabhd2...@gmail.com wrote: @Ankur.. I will try to explain the approach with an example.. Say the given matrix (sorted row wise and column wise) is as follows: a1 a2a3 a4 b1 b2b3 b4 c1 c2c3 c4 d1 d2d3 d4 Now, we want to sort the 2D array such that when all the rows are aligned sequentially it should result in a sorted sequence.. i.e. F1F2F3F4 . F13 F14 F15 F16 such that F1 = F2 == F16.. Now, let take each row at a time and ensure that that row contains all the elements as expected in the output matrix.. Row - 1 : M[0][0] = a1, which is at the correct place.. hence we won't touch it.. Now our task is to pick the second smallest no. in the matrix and place it at M[0][1].. Currently, M[0][1] is the second smallest in Row-1, but we are not sure whether its the second smallest in the entire matrix.. Hence, only way we can check that is to look in the submatrix (M[1][0] -- M[3][3]) Now, as we know that in the submatrix enclosed within (M[1][0] -- M[3] [3]) the smallest element present in this submatrix is positioned at M[1][0], therefore we will check M[0][1] against M[1][0].. If M[0][1] = M[1][0], that means M[0][1] has the second smallest element in the entire matrix.. else M[1][0] is the second smallest element in the entire matrix and we will swap M[1][0] with M[0][1].. Now, there are few things we need ensure if we end up swapping the values: 1) After swapping M[0][1]'s new value will be smaller than its original value, therefore the following is still valid: M[0][1] = M[0][2] =M[0][3] and also as M[0][1]'s new value was previously placed below M[0][0], hence it is = M[0][0] .. that means after swapping Row-1 still mains the sorted order... 2) Old value of M[1][0] = M[1][1].. Hence, the new value of M[0][1] is still = M[1][1].. therefore the sorted order of Column-2 is still valid... 3) Now, new value of M[1][0] = M[0][0] as an impact of old value of M[0][1] = M[0][0] Also, new value of M[1][0] = M[1][1] as an impact of old value of M[0][1] = M[1][1].. [ point 3 can be proved by the using the explanation from points 1 2.. 4) Now the only thing that we need to ensure is that Column - 1 is in sorted order i.e M[1][0] (new) = M[2][0] (old).. If the above is true that means the submatrix enclosed within (M[1][0] -- M[3][3]) is stabalized and has the row/column wise sorted order property in place... What if its not ?? then we need to readjust the submatrix ... Once we do that we are done for the current iteration.. [ we will talk abt stabalization in sometime..
Re: [algogeeks] Re: sort 2D array
I thought of a simpler algo, i m using the property of this matrix That is. a[i][0] is smallest of a[i][] and a[i+1][]so on,so to decide next smallest element i will only consider a[i][0]... i will swap element if required and sort the row(too by swapping) if element are changed. on the above example 1 3 4 8 9 1 2 4 8 91 2 3 4 9 1 2 3 4 9 1 2 3 4 5 1 2 3 4 5 2 5 18 25 50 3 5 18 25 50 8 5 18 25 50 sorting 5 8 18 25 50 9 8 18 25 50 8 9 18 25 50 6 7 22 45 55 ---.---.......---6 7 22 45 55 1 2 3 4 5 1 2 3 4 5 6 9 18 25 50 6 9--- 8 7 22 45 55--- 7 8 22.and so on... for swapping without space use a=a+b; b=a-b; a=a-b; it worked for examples i had takenpls notice me if any flaw with this.. On 1/11/12, Lucifer sourabhd2...@gmail.com wrote: @atul.. Complexity of heapifying(basically re-stabalizing the heap) is (m - i + j) when an element A[i][j] is swapped with A[i+1][0] as an impact of A[i][j] A[i+1][0].. On Jan 11, 4:44 pm, Dipit Grover dipitgro...@gmail.com wrote: @Shady : you would definitely need two index variables for each array I feel. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort 2D array
I thought of a simpler algo, i m using the property of this matrix That is. a[i][0] is smallest of a[i][] and a[i+1][]so on,so to decide next smallest element i will only consider a[i][0]... i will swap element if required and sort the row(too by swapping) if element are changed. on the above example 1)1 3 4 8 9 2 5 18 25 50 6 7 22 45 55 2) 1 2 4 8 9 3 5 18 25 50 3) 1 2 3 4 9 8 5 18 25 50 ... sorting 4) 1 2 3 4 9 5 8 18 25 50 .- 5) 1 2 3 4 5 9 8 18 25 50 .. 6) 1 2 3 4 5 8 9 18 25 50 6 7 22 45 55 7) 1 2 3 4 5 8) 1 2 3 4 5 6 9 18 25 50 6 9--- 8 7 22 45 55--- 7 8 22.and so on... for swapping without space use a=a+b; b=a-b; a=a-b; it worked for examples i had takenpls notice me if any flaw with this.. On 1/11/12, pankajsingh psingh...@gmail.com wrote: srry some formatting problem...i will repost later... -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
