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.
Re: [algogeeks] Re: Sort - Consecutive Array in O(n)
If the range is (0,n) then we can solve in O(n) TC and O(1) SC.
int checkconsequtive(int a[],int n){
if(n1)
return 0;
int min=a[0];
int max=a[0];
int i=0;
for(i=1;in;i++)
{
if(a[i]min)
min=a[i];
if(a[i]max)
max=a[i];
}
if(max-min+1!=n)
return 0;
for(i=0;in;i++)
{
if(a[a[i]-min]0)
return 0;
a[a[i]-min]=-a[a[i]-min];
}
for(i=0;in;i++)
a[i]=-a[i];
return 1;}
On Wed, Jul 6, 2011 at 3:46 PM, Gaurav Tyagi cho...@gmail.com wrote:
a) Find min(A). - O(n)
b) Find max(A) - O(n)
c) Calculate sum of natural numbers starting from min(A) to max(A) -
O(n)
d) Calculate sum of all numbers in the array. - O(n)
e) If sum in step c) is not same as sum in step d), then elements are
not consecutive. If the sum is same, then they are consecutive.
Can anyone think of a counterexample that breaks the above algo.
On Jul 6, 8:25 am, Sathaiah Dontula don.sat...@gmail.com wrote:
How about doing like this ?.
Without loss of generality, I can assume that numbers starts from 1
(if not, if it starts from ZERO, add by 1 to all the numbers,
if it is negative, find the min value, assume it is X, add by (-X)+1))
Now assume numbers are M, compute the product of the numbers and compute
M!
and check if they are equal.
does it work ?
Thanks,
Sathaiah
On Wed, Jul 6, 2011 at 11:45 AM, Anantha Krishnan
ananthakrishnan@gmail.com wrote:
Check this
*int isconsecutive(int a[], int n) {*
*if (n 1) {*
*return 0;*
*}*
*int max = a[0], min = a[0];*
*int i = 0;*
*
*
*int *hash = (int*) calloc(n, sizeof (int));*
*
*
*//find min and max from the array*
*for (i = 1; i n; i++) {*
*if (a[i] min)*
*min = a[i];*
*else if (a[i] max)*
*max = a[i];*
*}*
*
*
*if (max - min + 1 != n)*
*return 0;*
*
*
*for (i = 0; i n; i++) {*
*if (hash[a[i] - min + 1] == 1)*
*return 0;*
*hash[a[i] - min + 1] = 1;*
*}*
*return 1;*
*
*
*}*
*
*
*int main(int argc, char** argv) {*
*
*
*int a[] = {-1, 0,1,2, 4, 3, 5};*
*int n = sizeof (a) / sizeof (a[0]);*
*printf(%d, isconsecutive(a, n));*
*
*
*return (EXIT_SUCCESS);*
*}*
On Sat, Jun 25, 2011 at 1:14 AM, ross jagadish1...@gmail.com wrote:
Given an array, A, find if all elements in the sorted version of A are
consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive --
true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive -
false
--
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.
--
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 - Consecutive Array in O(n)
@sunny I dont understand the final checking part..Can u pls explain. On Sun, Jul 3, 2011 at 5:48 AM, Gene gene.ress...@gmail.com wrote: You can use a count sort, but you need an array to store the counts. The oppilas algorithm needs only constant extra storage. On Jun 30, 7:23 am, hary rathor harry.rat...@gmail.com wrote: can we not use count sort because of O(n) .? -- 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. -- Regards, Ganga Kameswaran Mobile: 7708876031 -- 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 - Consecutive Array in O(n)
can we not use count sort because of O(n) .? -- 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 - Consecutive Array in O(n)
will this work.
n size of array.
cal (a[i] - min(arr) + 1).
now cal sum of a[i], cal square sum of array as (a[i] * a[i]) , cal cube sum
of array as (a[i] * a[i] * a[i]). now if array elements are consecutive then
sum must be n * (n + 1) / 2. square sum must be (n * (n + 1) * (2n + 1) )/ 6
and cube sum must be (n * (n + 1) / 2) ^ 2.
On Fri, Jun 24, 2011 at 11:00 PM, Adarsh s.adars...@gmail.com wrote:
I think I got an work around for this if number of elements are
not odd why not make them odd :)
I variation to my prev algo
int n = A.size();
for (int i=0; in; i++)
total += A[i];
findMinMax(A[1...n]); //returns first smallest (fmin), second smallest
(smin) and largest (max) element in array
int fmean = (max+fmin)/2;
int smean = (max+smin)/2;
stotal = total - fmin;
if ((total - n*fmean) == 0)
{
if ((stotal - n*smean) == 0)
printf(consecutive\n);
return;
}
printf(not consecutive\n);
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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 - Consecutive Array in O(n)
My approach :
1. Find the median.
1.5 Check if the median is min + (max - min ) / 2.
2. Partition the array into two sub arrays using the partition function of
quicksort.
3. Check if the subarrays also satisfy the constraint.
Complexity : T(n) = 2 T(n/2) + O(1) :: O(nlogn)
On Sat, Jun 25, 2011 at 12:15 PM, varun pahwa varunpahwa2...@gmail.comwrote:
will this work.
n size of array.
cal (a[i] - min(arr) + 1).
now cal sum of a[i], cal square sum of array as (a[i] * a[i]) , cal cube
sum of array as (a[i] * a[i] * a[i]). now if array elements are consecutive
then sum must be n * (n + 1) / 2. square sum must be (n * (n + 1) * (2n + 1)
)/ 6 and cube sum must be (n * (n + 1) / 2) ^ 2.
On Fri, Jun 24, 2011 at 11:00 PM, Adarsh s.adars...@gmail.com wrote:
I think I got an work around for this if number of elements are
not odd why not make them odd :)
I variation to my prev algo
int n = A.size();
for (int i=0; in; i++)
total += A[i];
findMinMax(A[1...n]); //returns first smallest (fmin), second smallest
(smin) and largest (max) element in array
int fmean = (max+fmin)/2;
int smean = (max+smin)/2;
stotal = total - fmin;
if ((total - n*fmean) == 0)
{
if ((stotal - n*smean) == 0)
printf(consecutive\n);
return;
}
printf(not consecutive\n);
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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.
--
regards,
chinna.
--
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 - Consecutive Array in O(n)
1 thing i forgot to mention in my above post that at first i will also check
max - min + 1 must be equal to n. then only move further else the array will
not be consecutive after sort.
I think it will give correct output. please tell if any counter example.
On Sat, Jun 25, 2011 at 2:29 AM, pacific :-) pacific4...@gmail.com wrote:
My approach :
1. Find the median.
1.5 Check if the median is min + (max - min ) / 2.
2. Partition the array into two sub arrays using the partition function of
quicksort.
3. Check if the subarrays also satisfy the constraint.
Complexity : T(n) = 2 T(n/2) + O(1) :: O(nlogn)
On Sat, Jun 25, 2011 at 12:15 PM, varun pahwa varunpahwa2...@gmail.comwrote:
will this work.
n size of array.
cal (a[i] - min(arr) + 1).
now cal sum of a[i], cal square sum of array as (a[i] * a[i]) , cal cube
sum of array as (a[i] * a[i] * a[i]). now if array elements are consecutive
then sum must be n * (n + 1) / 2. square sum must be (n * (n + 1) * (2n + 1)
)/ 6 and cube sum must be (n * (n + 1) / 2) ^ 2.
On Fri, Jun 24, 2011 at 11:00 PM, Adarsh s.adars...@gmail.com wrote:
I think I got an work around for this if number of elements are
not odd why not make them odd :)
I variation to my prev algo
int n = A.size();
for (int i=0; in; i++)
total += A[i];
findMinMax(A[1...n]); //returns first smallest (fmin), second smallest
(smin) and largest (max) element in array
int fmean = (max+fmin)/2;
int smean = (max+smin)/2;
stotal = total - fmin;
if ((total - n*fmean) == 0)
{
if ((stotal - n*smean) == 0)
printf(consecutive\n);
return;
}
printf(not consecutive\n);
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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.
--
regards,
chinna.
--
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.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
People who fail to plan are those who plan to fail.
--
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 - Consecutive Array in O(n)
@Chinna: Your algorithm is simple quicksort with partition selection using medians. O(n log n) worst case. @Varun: You cannot prove that your algorithm will work for all cases. Hence, claiming a worst case bound of O(n) is incorrect. http://stackoverflow.mobi/question177118_Algorithm-to-determine-if-array-contains-n---n-m-.aspx -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/rRP-R-G2MM4J. 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 - Consecutive Array in O(n)
Divye Thanks for the link. Quoting the top answer from there. Under the assumption numbers less than one are not allowed and there are no duplicates, there is a simple summation identity for this - the sum of numbers from 1 to m in increments of 1 is (m * (m + 1)) / 2. You can then sum the array and use this identity. You can find out if there is a dupe under the above guarantees, plus the guarantee no number is above m or less than n (which can be checked in O(N)) The idea in pseudo-code: 0) Start at N = 0 1) Take the N-th element in the list. 2) If it is not in the right place if the list had been sorted, check where it should be. 3) If the place where it should be already has the same number, you have a dupe - RETURN TRUE 4) Otherwise, swap the numbers (to put the first number in the right place). 5) With the number you just swapped with, is it in the right place? 6) If no, go back to step two. 7) Otherwise, start at step one with N = N + 1. If this would be past the end of the list, you have no dupes. And, yes, that runs in O(N) although it may look like O(N ^ 2) On 6/26/11, DK divyekap...@gmail.com wrote: @Chinna: Your algorithm is simple quicksort with partition selection using medians. O(n log n) worst case. @Varun: You cannot prove that your algorithm will work for all cases. Hence, claiming a worst case bound of O(n) is incorrect. http://stackoverflow.mobi/question177118_Algorithm-to-determine-if-array-contains-n---n-m-.aspx -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/rRP-R-G2MM4J. 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 - Consecutive Array in O(n)
I have a solution that will do the job in O(n) time but will require three
variablesbut this solution won't work if the array contains -ve numbers.
*
int findrepeat(int a[],int n)
{
int i,xor = 0;
int min = findmin(a,n);
int max = findmax(a,n);
if((max-min+1)!=n)
return 0;
for(i = 0 ;in;i++)
xor^=a[i];
for(i=min;i=max;i++)
xor^=i;
if(xor)
return 0;
else
return 1;
}*
Please let me know if there is any counter example..
On Sat, Jun 25, 2011 at 1:17 AM, ross jagadish1...@gmail.com wrote:
One solution would be to : check if max-min = N and
that all elements are unique in the array.
However, this may require space complexity.. Looking for a
better solution.
On Jun 25, 12:44 am, ross jagadish1...@gmail.com wrote:
Given an array, A, find if all elements in the sorted version of A are
consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive --
true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive -
false
--
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.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *
--
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 - Consecutive Array in O(n)
Gene is correct :)
Counter example
{1, 2, 2, 5, 5}
See method 3 here http://geeksforgeeks.org/?p=11516
On 6/25/11, Gene gene.ress...@gmail.com wrote:
Nice idea, but unfortunately doesn't work. The XOR only contains
parity information. So just pick two values in the range and a low
order bit where they're different. Then swap the bits.
2 xor 3 xor 4 xor 5 = 0
Pick 3 and 4 and swap the lsb, which gives 2 and 5. So we have
2 xor 2 xor 5 xor 5 = 0
On Jun 24, 4:12 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
I have a solution that will do the job in O(n) time but will require three
variablesbut this solution won't work if the array contains -ve
numbers.
*
int findrepeat(int a[],int n)
{
int i,xor = 0;
int min = findmin(a,n);
int max = findmax(a,n);
if((max-min+1)!=n)
return 0;
for(i = 0 ;in;i++)
xor^=a[i];
for(i=min;i=max;i++)
xor^=i;
if(xor)
return 0;
else
return 1;
}*
Please let me know if there is any counter example..
On Sat, Jun 25, 2011 at 1:17 AM, ross jagadish1...@gmail.com wrote:
One solution would be to : check if max-min = N and
that all elements are unique in the array.
However, this may require space complexity.. Looking for a
better solution.
On Jun 25, 12:44 am, ross jagadish1...@gmail.com wrote:
Given an array, A, find if all elements in the sorted version of A are
consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive --
true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive -
false
--
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.
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926*
--
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 - Consecutive Array in O(n)
@Adarsh
fails on this
a[] = {2,2,2,6,6,6}
On Sat, Jun 25, 2011 at 10:54 AM, Adarsh s.adars...@gmail.com wrote:
int n = A.size();
for (int i=0; in; i++)
total += A[i];
findMinMax(A[1...n]);
int mean = (max+min)/2;
if ((total - n*mean) == 0)
printf(consecutive\n);
else
printf(not consecutive\n);
findMixMax() ... this can be done in O(n)
so, total time complexity ... O(n)
works for negative numbers also if there is any mistake ... let me
know
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 - Consecutive Array in O(n)
@adarsh
no it will Fails for both even and odd no of elemets
a[] = {2,2,2,4,6,6,6}
seems like we need to check for the presence of each no between min to max
using a good hashing approach.
On Sat, Jun 25, 2011 at 11:20 AM, Adarsh s.adars...@gmail.com wrote:
Missed that... also, my method seems to work only if number of
elements are odd.
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 the array
Reverse the 2nd part of the Array so that they are sorted in descending order. Then apply bitonic sort On Wed, Jun 22, 2011 at 2:34 PM, ross jagadish1...@gmail.com wrote: @himanshu: I dont think, the approach works, in present form. in place merge sort or insertion sort is fine. Test with, 12 13 19 16 and 0 20 10 14 as 2 parts of the array. On Jun 22, 8:42 am, Sriganesh Krishnan 2448...@gmail.com wrote: ya...we can do it in O(n) n time!!! nice question! On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal himanshukansal...@gmail.com wrote: @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two ptrs one at the beginning and one intitially pointing to middle of the array... thn compare the elemnts pointed by them and swap the values if necesary nd incremnt d ptr as u go on... ths vl tk (n/2)+(n/2)-1 =O(n) time corrct me if m wrong On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.com wrote: its like inplace mergesort On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.com wrote: you have an array of size n where first n/2 is sorted and the sencond half is sorted . You need to sort the entire array inplace Its second modification version is where first part is sorted and other is NOT sorted . You need to make entire sorted . -- Regards,* Aanchal Goyal*. -- 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. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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 the array
Let the array elements be 2,3,5,10 1,4,8,12. Have two index variables m and n. Intially m will point to 2 and n to 1. 1. Compare the elements in m and n. 2. If elem[m] elem[n] swap, increment n 3. else increment m and go to step 1. 4. end if m becomes the starting value of n or n reaches end of array. Think it should work. On Wed, Jun 22, 2011 at 4:05 PM, Algoose chase harishp...@gmail.com wrote: Reverse the 2nd part of the Array so that they are sorted in descending order. Then apply bitonic sort On Wed, Jun 22, 2011 at 2:34 PM, ross jagadish1...@gmail.com wrote: @himanshu: I dont think, the approach works, in present form. in place merge sort or insertion sort is fine. Test with, 12 13 19 16 and 0 20 10 14 as 2 parts of the array. On Jun 22, 8:42 am, Sriganesh Krishnan 2448...@gmail.com wrote: ya...we can do it in O(n) n time!!! nice question! On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal himanshukansal...@gmail.com wrote: @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two ptrs one at the beginning and one intitially pointing to middle of the array... thn compare the elemnts pointed by them and swap the values if necesary nd incremnt d ptr as u go on... ths vl tk (n/2)+(n/2)-1 =O(n) time corrct me if m wrong On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.comwrote: its like inplace mergesort On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.com wrote: you have an array of size n where first n/2 is sorted and the sencond half is sorted . You need to sort the entire array inplace Its second modification version is where first part is sorted and other is NOT sorted . You need to make entire sorted . -- Regards,* Aanchal Goyal*. -- 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. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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. -- --Navneet -- 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 the array
On Wed, Jun 22, 2011 at 8:38 PM, oppilas . jatka.oppimi...@gmail.comwrote: On Wed, Jun 22, 2011 at 8:20 PM, Navneet Gupta navneetn...@gmail.comwrote: Let the array elements be 2,3,5,10 1,4,8,12. Have two index variables m and n. Intially m will point to 2 and n to 1. 1. Compare the elements in m and n. 2. If elem[m] elem[n] swap, increment n *I think it should be increment m. * ** 3. else increment m and go to step 1* /*Increment in n here*/*. 4. end if m becomes the starting value of n or n reaches end of array. Think it should work. On Wed, Jun 22, 2011 at 4:05 PM, Algoose chase harishp...@gmail.com wrote: Reverse the 2nd part of the Array so that they are sorted in descending order. Then apply bitonic sort On Wed, Jun 22, 2011 at 2:34 PM, ross jagadish1...@gmail.com wrote: @himanshu: I dont think, the approach works, in present form. in place merge sort or insertion sort is fine. Test with, 12 13 19 16 and 0 20 10 14 as 2 parts of the array. On Jun 22, 8:42 am, Sriganesh Krishnan 2448...@gmail.com wrote: ya...we can do it in O(n) n time!!! nice question! On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal himanshukansal...@gmail.com wrote: @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two ptrs one at the beginning and one intitially pointing to middle of the array... thn compare the elemnts pointed by them and swap the values if necesary nd incremnt d ptr as u go on... ths vl tk (n/2)+(n/2)-1 =O(n) time corrct me if m wrong On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.comwrote: its like inplace mergesort On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.com wrote: you have an array of size n where first n/2 is sorted and the sencond half is sorted . You need to sort the entire array inplace Its second modification version is where first part is sorted and other is NOT sorted . You need to make entire sorted . -- Regards,* Aanchal Goyal*. -- 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. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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. -- --Navneet -- 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 the array
This problem can also be done by using Merging function as in the merge
sort.
1. Copy the sorted elements of the first half in one array (arr L) and
second half in another (arr R). Original array N.
2. count vary from 1 to n.
if (L[i] R[j] ) { N[count] = L[i], i++}
else { N[count] = R[j] , j++}
count++
3. copy the rest of the elements from the remaining (either L or R whichever
is remaining)
Time complexity O(n)
Plz correct me if I m wrong.
--
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 the array
@ankit: we need an inplace algorithm :) -- 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.
