Re: [algogeeks] Re: Sort 7 numbers of 4 digits each
Its radix sort.. On Fri, Aug 3, 2012 at 4:39 PM, Navin Gupta navin.nit...@gmail.com wrote: I think the no. of comparisons depend upon the type of sorting used. Please specify the sorting algorithm used:- 1:- in case of bubble sort it is - 21 2:- in case of radix sort it is - 84 On Tuesday, 31 July 2012 21:21:30 UTC+5:30, Sambhavna Singh wrote: Hi, We need to sort 7 numbers each of 4 digits. What is the number of comparisons in worst case . Options are as follows: 1) 40 2) 38 3) 47 4) 280 Please also explain why so? -- 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/-/sjJWIN8eNHIJ. 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.
[algogeeks] Re: Sort
On Tuesday, 13 July 2010 17:32:43 UTC-7, Gene wrote:
On Jul 13, 2:46 pm, Devendra Pratap Singh dpsingh.ii...@gmail.com
wrote:
@gene
thanx for the working code
but can u explain its working more clearly
On Jul 13, 11:21 pm, Gene gene.ress...@gmail.com wrote:
On Jul 10, 5:18 pm, Gene gene.ress...@gmail.com wrote:
On Jul 9, 3:55 pm, Devendra Pratap Singh dpsingh.ii...@gmail.com
wrote:
plz write a code to
Sort n integer in the range 1 to n^2 in O(n)
Use radix sort with radix n. Three O(n) passes will always do the
job. If you subtract 1 from each value so the range is 0 to n^2-1,
two
passes will be enough.
Nice lunchtime puzzle. Here is some code for your pleasure:
#include stdio.h
#include stdlib.h
#define MAX_SIZE (10 * 1024)
struct node_s {
int next, val;
} nodes[MAX_SIZE];
// Radix-n sort descending. Assumes data are non-negative.
// Will take K passes if largest datum does not exceed n^K.
int sort_descending(struct node_s *nodes, int n)
{
int i, k, head, next, shifted, digit, more_p, n_passes, div;
int buckets[MAX_SIZE];
// Chain nodes into a single list.
head = 0;
for (i = 0; i n; i++)
nodes[i].next = i + 1;
nodes[n - 1].next = -1;
// Make passes until all remainders are zero.
// Always 2 if max datum is less than n^2.
n_passes = 0;
div = 1;
do {
// Empty the buckets.
for (k = 0; k n; k++)
buckets[k] = -1;
// Fill the buckets, noting whether we need more passes.
more_p = 0;
for (i = head; i != -1; i = next) {
next = nodes[i].next;
shifted = nodes[i].val / div;
digit = shifted % n;
nodes[i].next = buckets[digit];
buckets[digit] = i;
if (shifted = div) more_p = 1;
}
// Concatenate the buckets.
head = -1;
for (k = 0; k n; k++) {
for (i = buckets[k]; i != -1; i = next) {
next = nodes[i].next;
nodes[i].next = head;
head = i;
}
}
n_passes++;
div *= n;
} while (more_p);
printf(sort took %d passes\n, n_passes);
return head;
}
int main(void)
{
int i, n, head, last;
n = 500;
for (i = 0; i n; i++)
nodes[i].val = rand() % (n * n);
head = sort_descending(nodes, n);
// Make sure we're sorted descending and print.
last = -1;
for (i = head; i != -1; i = nodes[i].next) {
printf(%d , nodes[i].val);
if (last != -1 nodes[i].val last) {
printf(oops!\n);
return 1;
}
last = nodes[i].val;
}
printf(\n);
return 0;
}
Google for radix sort. After reading the Wikipedia article, the
comments in the code should make sense. We're building the radix
buckets as singly linked lists and then concatenating all the lists to
implement the merge pass.
--
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/-/cuP64D_wx8AJ.
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 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.
[algogeeks] Re: sort 2D array
@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.
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.
[algogeeks] Re: sort 2D array
@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.
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.
[algogeeks] Re: sort 2D array
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.
?#include stdio.h
#define ROWS 3
#define COLS 5
void swap(int *a, int *b)
{
/*swap numbers a b*/
int temp = *a;
*a = *b;
*b = temp;
}
void print_array(int *arr)
{
/*prints the two dimensional array arr*/
int i,j;
for(i=0;iROWS;i++)
{
for(j=0;jCOLS;j++)
{
printf( %d ,arr[COLS*i + j]);
}
printf(\n);
}
}
int min(int a, int b)
{
/*Finds the minimum of a and b*/
if(ab)
return a;
return b;
}
void adjustrow(int *arr,int cur_row,int cur_col)
{
/*adjusts the row in ascending order*/
if(arr[COLS*cur_row + cur_col+1] = arr[COLS*cur_row + cur_col]) //elem in next column is greater
return;
swap(arr[COLS*cur_row + cur_col+1],arr[COLS*cur_row + cur_col]);
adjustrow(arr,cur_row,cur_col+1);
}
void adjustcol(int *arr,int cur_row,int cur_col)
{
/*adjusts the column in asceding order*/
if(arr[COLS*(cur_row+1) + cur_col] = arr[COLS*cur_row + cur_col]) //elem in next row is greater
return;
swap(arr[COLS*(cur_row+1) + cur_col],arr[COLS*cur_row + cur_col]);
adjustcol(arr,cur_row+1,cur_col);
}
void readjust(int *arr,int cur_row, int cur_col)
{
/*re-adjusts the array so that the initial property of ascending rows and columns is maintained*/
if(cur_row == ROWS-1) //into the last row
{
adjustrow(arr,cur_row,cur_col);
return;
}
if(cur_col == COLS -1) //into the last column
{
adjustcol(arr,cur_row,cur_col);
return;
}
//new elem in right place
if(arr[COLS*cur_row + cur_col] = min(arr[COLS*(cur_row+1) + cur_col],arr[COLS*(cur_row) + cur_col+1]))
return;
int new_cur_row = arr[COLS*(cur_row+1) + cur_col] = arr[COLS*cur_row + cur_col+1] ? (cur_row+1) : cur_row;
int new_cur_col = arr[COLS*(cur_row+1) + cur_col] = arr[COLS*cur_row + cur_col+1] ? cur_col : (cur_col+1);
swap(arr[COLS*cur_row + cur_col],arr[COLS*new_cur_row + new_cur_col]);
readjust(arr[0],new_cur_row,new_cur_col);
}
void sort_whole_array(int *arr)
{
/*interface function for sorting the complete array*/
int i,j;
for(i=0;iROWS-1;i++)
{
for(j=1;jCOLS;j++)
{
if(arr[COLS*i + j] = arr[COLS*(i+1) + 0]) //arr[i][j] = arr[i+1][0]
continue;
swap(arr[COLS*i + j],arr[COLS*(i+1) + 0]); //swap(arr[i][j],arr[i+1][0])
readjust(arr[0],(i+1),0); //readjust(arr[i+1][0],i+1,0);
}
}
}
int main()
{
int arr[ROWS][COLS] = {{1,3,4,8,9},{2,5,18,25,50},{6,7,22,45,55}};
printf(\n==Input Array==\n);
print_array(arr[0][0]);
sort_whole_array(arr[0][0]);
printf(\n==Sorted Array==\n);
print_array(arr[0][0]);
return 0;
}
[algogeeks] Re: sort 2D array
Awesome!! -- 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/-/RsqwEYjbA3kJ. 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.
[algogeeks] Re: sort 2D array
Awesome Explanation Lucifer!! On Wednesday, January 11, 2012 10:25:01 PM UTC+5:30, Lucifer wrote: @Ankur.. I will try to explain the approach with an example.. -- 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/-/vzdaHYHzwfEJ. 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.
[algogeeks] Re: sort 2D array
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its subtrees share some nodes...
Now the point being that... say we select any index pair (i,j), we
know for the submatrix whose left-top corner is (i,j) and right-bottom
corner is (m,n) , he smallest element among all the elements in the
submatrix is positioned at (i,j) itself.. Same goes for largest
element which is positioned at (m,n).. Hence we can say that any
submatrix rooted at (i,j) acts as a min-heap...
Now, say if i replace A(i,j) with a value greater than A(i,j), then
heapifying the submatrix so that the sorted(row,col) order is restored
will take (m + n -i -j) max steps...basically either go down or go
left in case adjustment is required...
Keeping in mind the above heapifying property lets solve the actual
problem row wise...
Pseudocode:
for ( int row = 0; row N; ++row)
for (int col =0; col N; ++col)
{
if (A[row][col] A[row+1][0])
{
swap (A[row][col] , A[row+1][0])
heapify/readjust (submatrix rooted at A[row+1][0] )
}
}
I think the above shall work...
What do u guys think??
Say, no of rows = m and no. of cols = n,
Time complexity = sum over all i (1 to M} { i*(M+N-i) }
= O(M^3) ...
In case M N,
then we can follow the same process column-wise and the time
complexity would be O(N^3)..
On Jan 11, 1:35 pm, Sanjay Rajpal sanjay.raj...@live.in wrote:
Where do we store the sorted list ? How do we do it in place ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal sanjay.raj...@live.inwrote:
How can it be mn log mn ?
it will be O(mn) as we elements are sorted, we simply pick minimum at each
iteration of the loop. Since there are mn elements, so complexity will be
O(mn).
Correct me if m wrong.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:29 AM, Ankur Garg ankurga...@gmail.com wrote:
If we use K merge I think the time complexity would be nm lognm
I think we must try doing in O(m*n)
On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote:
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal
sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such a
way that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Tue, Jan 10, 2012 at 11:28 PM, prakash y
yprakash@gmail.comwrote:
sort the whole matrix in ascending array means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.com
wrote:
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in ascending array.
We cannot use extra space.
--
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.
--
[algogeeks] Re: sort 2D array
@correction:
/*
basically either go down or go
*right* in case adjustment is required...
*/
On Jan 11, 1:56 pm, Lucifer sourabhd2...@gmail.com wrote:
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its subtrees share some nodes...
Now the point being that... say we select any index pair (i,j), we
know for the submatrix whose left-top corner is (i,j) and right-bottom
corner is (m,n) , he smallest element among all the elements in the
submatrix is positioned at (i,j) itself.. Same goes for largest
element which is positioned at (m,n).. Hence we can say that any
submatrix rooted at (i,j) acts as a min-heap...
Now, say if i replace A(i,j) with a value greater than A(i,j), then
heapifying the submatrix so that the sorted(row,col) order is restored
will take (m + n -i -j) max steps...basically either go down or go
left in case adjustment is required...
Keeping in mind the above heapifying property lets solve the actual
problem row wise...
Pseudocode:
for ( int row = 0; row N; ++row)
for (int col =0; col N; ++col)
{
if (A[row][col] A[row+1][0])
{
swap (A[row][col] , A[row+1][0])
heapify/readjust (submatrix rooted at A[row+1][0] )
}
}
I think the above shall work...
What do u guys think??
Say, no of rows = m and no. of cols = n,
Time complexity = sum over all i (1 to M} { i*(M+N-i) }
= O(M^3) ...
In case M N,
then we can follow the same process column-wise and the time
complexity would be O(N^3)..
On Jan 11, 1:35 pm, Sanjay Rajpal sanjay.raj...@live.in wrote:
Where do we store the sorted list ? How do we do it in place ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal
sanjay.raj...@live.inwrote:
How can it be mn log mn ?
it will be O(mn) as we elements are sorted, we simply pick minimum at each
iteration of the loop. Since there are mn elements, so complexity will be
O(mn).
Correct me if m wrong.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:29 AM, Ankur Garg ankurga...@gmail.com wrote:
If we use K merge I think the time complexity would be nm lognm
I think we must try doing in O(m*n)
On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote:
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal
sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such a
way that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Tue, Jan 10, 2012 at 11:28 PM, prakash y
yprakash@gmail.comwrote:
sort the whole matrix in ascending array means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.com
wrote:
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in ascending array.
We cannot use extra space.
--
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
[algogeeks] Re: sort 2D array
@correction..
for ( int row = 0; row *M*; ++row)
On Jan 11, 1:56 pm, Lucifer sourabhd2...@gmail.com wrote:
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its subtrees share some nodes...
Now the point being that... say we select any index pair (i,j), we
know for the submatrix whose left-top corner is (i,j) and right-bottom
corner is (m,n) , he smallest element among all the elements in the
submatrix is positioned at (i,j) itself.. Same goes for largest
element which is positioned at (m,n).. Hence we can say that any
submatrix rooted at (i,j) acts as a min-heap...
Now, say if i replace A(i,j) with a value greater than A(i,j), then
heapifying the submatrix so that the sorted(row,col) order is restored
will take (m + n -i -j) max steps...basically either go down or go
left in case adjustment is required...
Keeping in mind the above heapifying property lets solve the actual
problem row wise...
Pseudocode:
for ( int row = 0; row N; ++row)
for (int col =0; col N; ++col)
{
if (A[row][col] A[row+1][0])
{
swap (A[row][col] , A[row+1][0])
heapify/readjust (submatrix rooted at A[row+1][0] )
}
}
I think the above shall work...
What do u guys think??
Say, no of rows = m and no. of cols = n,
Time complexity = sum over all i (1 to M} { i*(M+N-i) }
= O(M^3) ...
In case M N,
then we can follow the same process column-wise and the time
complexity would be O(N^3)..
On Jan 11, 1:35 pm, Sanjay Rajpal sanjay.raj...@live.in wrote:
Where do we store the sorted list ? How do we do it in place ?
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal
sanjay.raj...@live.inwrote:
How can it be mn log mn ?
it will be O(mn) as we elements are sorted, we simply pick minimum at each
iteration of the loop. Since there are mn elements, so complexity will be
O(mn).
Correct me if m wrong.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Wed, Jan 11, 2012 at 12:29 AM, Ankur Garg ankurga...@gmail.com wrote:
If we use K merge I think the time complexity would be nm lognm
I think we must try doing in O(m*n)
On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg ankurga...@gmail.com wrote:
@Shady Rows are already sorted ...
On Wed, Jan 11, 2012 at 1:53 PM, shady sinv...@gmail.com wrote:
^^ true, sort the rows and then a K-way merge.
On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal
sanjay.raj...@live.inwrote:
I guess sort the array such that elements are sorted finally in such a
way that if we print them row by row, the result is a sorted array.
K-way merge can be useful.
*
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
Contact: +91-8053566286
*
On Tue, Jan 10, 2012 at 11:28 PM, prakash y
yprakash@gmail.comwrote:
sort the whole matrix in ascending array means?
can you please explain ?
On Wed, Jan 11, 2012 at 12:53 PM, atul anand atul.87fri...@gmail.com
wrote:
Given 2D array.
The rows are sorted in ascending order and the colums are sorted in
ascending order.
We have to sort the whole matrix in ascending array.
We cannot use extra space.
--
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
[algogeeks] Re: sort 2D array
@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.
[algogeeks] Re: sort 2D array
@All...
Infact if we closely observe, then for A[row][col] when replaced with
A[row+1][0].. Then on heapifying the matrix rooted at A[row+1][0], the
new value will have shifts within the submatrix (A[row+1][0] , A[M]
[col])
Hence, the actual time complexity would be :
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M}
{
sum over all j (1 to N}
{
(M - i + j)
}
}
= M*N*(M + N)/2
On Jan 11, 2:27 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.
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.
[algogeeks] Re: sort 2D array
@shady.. Look out for in-place merge sort... On Jan 11, 4:23 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.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
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.
[algogeeks] Re: sort 2D array
@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.
[algogeeks] Re: sort 2D array
@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.
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.
[algogeeks] Re: sort 2D array
@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 Row -1.. we have the first 4 smallest elements
in place and we move on to the next row and follow a same process..
For ex-
Row -2
M[1][0] is already in place and has the 5th largest element..
Hence, lets look at M[1][1].. For this we will consider the submatrix
at (M[2][0] -- M[3][3]) and follow the same steps as
above..
---
Now lets talk abt how to stabilize the submatrix when the top-left
corner of the submatrix is replaced with another value...
Say the given matrix 'R' to be stabilized is:
a b c
d e f
g h i
Now. if 'a' replaced with 'x'...
x b c
d e f
g h i
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))
}
Once, we break out of the while loop, we know that the matrix has been
stabilized and also R[0][0] has the smallest value..
// Observe that either 'x' shifts to the right position or to the
position just below it..
// Hence, whats the max. no. of shifts that 'x' can have.??
// no. of columns + no. of rows...
// Hence, heapifying time is (no. of columns + no. of rows)
Additional explanation:
Now, for matrix R[0][0], its childs when interpreted as a heap are
located at R[0][1] and R[1][0]...
Now, we know for sure that, the submatrix (R[0][1]... R[M][N]) has the
smallest element at R[0][1]..
Similarly, submatrix (R[1][0]... R[M][N]) has the smallest element at
R[1][0]...
If you observe closely then:
Elements in submatrix (R[0][0]... R[M][N])
=
Elements in submatrix (R[0][1]... R[M][N])
U
Elements in submatrix (R[1][0]... R[M][N])
U
R[0][0]..
Looking at the above equation we can say that, if R[0][0] has been
replaced and not the smallest element, then the smallest element will
be one of (R[1][0] or R[0][1] )..
And this rule applies as
[algogeeks] Re: sort 2D array
@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 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 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.
F1 F2 F3 F4
.
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 Row -1.. we have the first 4 smallest elements
in place and we move on to the next row and follow a same process..
For ex-
Row -2
M[1][0] is already in place and has the 5th largest element..
Hence, lets look at M[1][1].. For this we will consider the submatrix
at (M[2][0] -- M[3][3]) and follow the same steps as
above..
---
Now lets talk abt how to stabilize the submatrix when the top-left
corner of the submatrix is replaced with another value...
Say the given matrix 'R' to be stabilized is:
a b c
d e f
g h i
Now. if 'a' replaced with 'x'...
x b c
d e f
g h i
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
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..
[algogeeks] Re: sort 2D array
@atul.. Yup, its incorrect... because as i said.. for A[i][j] its children are at A[i+1][j] and A[i][j+1].. Hence, if u look at the array as a 1D array, then your LEFT and RIGHT indices would be incorrect... Also, For any A[i][j], if it doesn't hold the correct value then the min element is always picked from A[i+1][0] and then we heapify submatrix rooted at A[i+1][0].. Nyways i think you have got this part.. but just thought of reclarifying... Let me know if u have any doubt... On Jan 11, 10:37 pm, atul anand atul.87fri...@gmail.com wrote: @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 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 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. F1 F2 F3 F4 . 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)
[algogeeks] Re: sort 2D array
@atul.. Missed ur previous post by a couple of mins.. Nyways it seems u got it .. :).. On Jan 11, 10:44 pm, Lucifer sourabhd2...@gmail.com wrote: @atul.. Yup, its incorrect... because as i said.. for A[i][j] its children are at A[i+1][j] and A[i][j+1].. Hence, if u look at the array as a 1D array, then your LEFT and RIGHT indices would be incorrect... Also, For any A[i][j], if it doesn't hold the correct value then the min element is always picked from A[i+1][0] and then we heapify submatrix rooted at A[i+1][0].. Nyways i think you have got this part.. but just thought of reclarifying... Let me know if u have any doubt... On Jan 11, 10:37 pm, atul anand atul.87fri...@gmail.com wrote: @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 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 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. F1 F2 F3 F4 . 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
[algogeeks] Re: sort 2D array
@Lucifer, I was thinking in the similar lines, but, I couldn't get the exact way of re-arranging the sub-matrix, Please throw some inputs or links which can solve that Rearrange in O(M+N) time. Problem I see: when we identify the position for a[i+1][0], and we repace it with a[k][l], the a[k][l] which is now in a[i+1][0] must again be searched for its exact position example: -- current state 1 2 7 3 5 8 4 6 9 -- updating a[i+1][0] 1 2 3 7 5 8 4 6 9 -- assuming we try to fix the value in row first.. and then check column.. (and may be recursively) 1 2 3 5 7 8 -- now here there are two in consistancies (5,4 in col1, 7,6 in col2) 4 6 9 1 2 3 4 7 8 5 6 9 and 1 2 3 4 6 8 5 7 9 == or we doing this approach? and will this work? the choice that replaces 7 in this case is min of (5,4) 1 2 3 7 5 8 4 6 9 and.. recursively keep replacing the min (right, next-row_first-col) with the current, (this one is expected to take O(M+N-i-j) as u mentioned.) -- 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/-/b8NPQMRwoD0J. 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.
[algogeeks] Re: sort 2D array
@sravan and Ashish.. In the second half of the post that starts with.. /* @Ankur.. I will try to explain the approach with an example.. */ i have explained how the heap-readjustment will work.. --- Plz go thru it and let me know if further clarification is required... On Jan 11, 10:50 pm, Ashish Goel ashg...@gmail.com wrote: heapify/readjust (submatrix rooted at A[row+1][0] ) how do we do this the element moved as part of swap may fit in anywhere in submatrixrow+1,0 to m,n Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jan 11, 2012 at 11:14 PM, Lucifer sourabhd2...@gmail.com wrote: @atul.. Yup, its incorrect... because as i said.. for A[i][j] its children are at A[i+1][j] and A[i][j+1].. Hence, if u look at the array as a 1D array, then your LEFT and RIGHT indices would be incorrect... Also, For any A[i][j], if it doesn't hold the correct value then the min element is always picked from A[i+1][0] and then we heapify submatrix rooted at A[i+1][0].. Nyways i think you have got this part.. but just thought of reclarifying... Let me know if u have any doubt... On Jan 11, 10:37 pm, atul anand atul.87fri...@gmail.com wrote: @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 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 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. F1 F2 F3 F4 . 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,
[algogeeks] Re: sort 2D array
@Lucifer: great explanation. and very good idea that the matrix is like a 'heap' I didn't see your post.. not I get it.. :) -- 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/-/MaqW8RiE8JwJ. 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 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.
[algogeeks] Re: Sort problem
Bitonic sort On Aug 31, 11:26 am, bharatkumar bagana bagana.bharatku...@gmail.com wrote: while increasing ... we have to use insertion sort which is in place algo .. while decreasing... any way that is sorted one .. so no need to maintain ... But it takes O(n^2) time .. On Wed, Aug 31, 2011 at 1:58 AM, Navneet Gupta navneetn...@gmail.comwrote: Given an array of size n wherein elements keep on increasing monotically upto a certain location after which they keep on decreasing monotically, then again keep on increasing, then decreasing again and so on. Sort the array in place (ie. using only O(1) extra memory) -- Regards, 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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 IT
@dave, ur converting array values into baseN and doing radix?
then every time there will be N*N = 100(baseN).
i think ur code doesn't works as ur checking against msd first(/) , then
lsd(%)
we need to exchange these operations, then it works fine.
surender
On Wed, Aug 3, 2011 at 3:55 PM, Dave dave_and_da...@juno.com wrote:
@Arun: Look up Radix sort and then read the comments in the code.
Dave
On Aug 3, 4:23 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
yes dave it wud be better if u cud post an explanation of what u r doing
in
each step..thanks
On Wed, Aug 3, 2011 at 6:51 AM, payel roy smithpa...@gmail.com wrote:
@Dave,
Can you please explain the algo? It's getting very difficult to
understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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.- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort IT
@Surender: Yes. Actually, I'm converting a[i]-1 into radix N. The most
significant digit is (a[i]-1)/N, and the least significant digit is
(a[i]-1)%N. You are right that the lsd should be before the msd.
Thanks.
Dave
On Aug 11, 8:44 am, surender sanke surend...@gmail.com wrote:
@dave, ur converting array values into baseN and doing radix?
then every time there will be N*N = 100(baseN).
i think ur code doesn't works as ur checking against msd first(/) , then
lsd(%)
we need to exchange these operations, then it works fine.
surender
On Wed, Aug 3, 2011 at 3:55 PM, Dave dave_and_da...@juno.com wrote:
@Arun: Look up Radix sort and then read the comments in the code.
Dave
On Aug 3, 4:23 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
yes dave it wud be better if u cud post an explanation of what u r doing
in
each step..thanks
On Wed, Aug 3, 2011 at 6:51 AM, payel roy smithpa...@gmail.com wrote:
@Dave,
Can you please explain the algo? It's getting very difficult to
understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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.-Hide quoted text -
- Show quoted text -
--
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 IT
yes dave it wud be better if u cud post an explanation of what u r doing in
each step..thanks
On Wed, Aug 3, 2011 at 6:51 AM, payel roy smithpa...@gmail.com wrote:
@Dave,
Can you please explain the algo? It's getting very difficult to understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort IT
@Payel: Look up Radix sort and then read the comments in the code.
Dave
On Aug 2, 11:51 pm, payel roy smithpa...@gmail.com wrote:
@Dave,
Can you please explain the algo? It's getting very difficult to understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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.- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort IT
@Arun: Look up Radix sort and then read the comments in the code.
Dave
On Aug 3, 4:23 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
yes dave it wud be better if u cud post an explanation of what u r doing in
each step..thanks
On Wed, Aug 3, 2011 at 6:51 AM, payel roy smithpa...@gmail.com wrote:
@Dave,
Can you please explain the algo? It's getting very difficult to understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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.- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort IT
absolutely correct dudethat was the way i read in clrs in radix sort chap On Aug 2, 4:50 pm, Harshit Kapoor kapoor...@gmail.com wrote: I think that we can do it by first passing through an array once and convert all the interger to the base N in O(N). Since all elements are in the range 1 to N^2 they can have atmost 3 digits.Now apply radix sort which will be O( dn ) where d=3 in this case .= O(n) when done convert them back to decimal notation in O(N) . But here N must be maximum no of single digit characters representable in ur system. Check if possible On Tue, Aug 2, 2011 at 1:02 PM, payel roy smithpa...@gmail.com wrote: Can you please elaborate ?? On 2 August 2011 12:38, sunny agrawal sunny816.i...@gmail.com wrote: Radix sort is one of the solution. because this Question is in the section Radix sort in CLRS. :) On Tue, Aug 2, 2011 at 11:10 AM, Ravinder Kumar ravinde...@gmail.comwrote: I have little thought on this : divide the whole array by n and store their remainder also in an array now number in original array are in range 1-n sort the array and when two number with same break the tie using remainder array recreate the array using remainder array . -- *With Regards :* Ravinder Kumar B.Tech Final Year Computer Science and Engineering MNNIT Allahabad -- 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. -- 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.
[algogeeks] Re: Sort IT
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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 IT
@Dave,
Can you please explain the algo? It's getting very difficult to understand
the code ..
On 3 August 2011 01:14, Dave dave_and_da...@juno.com wrote:
@Pankaj: Assuming generously that by N^2 you mean N*N instead of N
exclusive-or 2, your very first statement is already O(N^2), as it
will take that long just to set the array to zero.
Here is a radix sort to sort an array x[N] containing values from 1 to
N*N in O(N):
int a[N], b[N], i;
// initialize and tally occurrences of first radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)/N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from array x to temp array b:
for( i = 0 ; i N ; ++i )
b[a[(x[i]-1)/N]++] = x[i];
// initialize and tally occurrences of second radix-N digit of x[i]-1:
for( i = 0 ; i N ; ++i )
a[i] = 0;
for( i = 0 ; i N ; ++i )
a[(x[i]-1)%N]++;
// compute starting point for each radix digit:
a[N-1] = N - a[N-1];
for( i = N-2 ; N = 0 ; --i )
a[i] = a[i+1] - a[i];
// move numbers from temp array b back to array x:
for( i = 0 ; i N ; ++i )
x[a[(x[i]-1)%N]++] = b[i];
// array is now sorted. Run time is O(N). Space is O(N).
Dave
On Aug 2, 11:04 am, pankaj kumar pancsen...@gmail.com wrote:
int a[N^2]={0},i,j;
for(i=0;iN^2;i++)
{
cinj;
a[j]++;
}
for(i=0;iN^2;i++)
{
if(a[i]!=0)
{
while(a[i]--)
{
couti\t;
}
}- Hide quoted text -
- Show quoted text -
--
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)
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
Your algorithm is good, but the first part doesn't help you because
duplicates are allowed.
Here is code that does what you say:
#include stdio.h
int main(void)
{
int a[] = { 6, 2, 4, 8, 7, 3, 5 };
int n = sizeof a / sizeof a[0];
int i, t, min, max, tmp;
min = max = a[0];
for (i = 1; i n; i++) {
if (a[i] min) min = a[i];
if (a[i] max) max = a[i];
}
if (min + n - 1 != max) {
printf(no\n);
return 1;
}
for (i = 0; i n; i++) {
while (a[i] != i + min) {
t = a[a[i] - min];
if (t == a[i]) {
printf(no\n);
return 1;
}
a[a[i] - min] = a[i];
a[i] = t;
}
}
for (i = 0; i n; i++)
printf(%d , a[i]);
printf(yes\n);
return 0;
}
On Jun 25, 11:22 pm, oppilas . jatka.oppimi...@gmail.com wrote:
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-ar...
--
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.- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
I was responding to oppilas. His use of the formula N(N+1)/2 really
doesn't help here. Hashing will work fine, but it's not the simplest
or most efficient way. Because you're testing for consecutive
integers, it makes more sense to use an array(min .. max) of booleans
to test for duplicates rather than a hash table. Set them all false
and then go through the data setting the corresponding boolean true
for each. If you are about to set one true and it's already set, you
have a duplicate.
The algorithm of oppilas cleverly substitutes a special ordering of
the original array for the array of booleans above. Swapping the i'th
largest integer to the i'th array position is the same as setting the
boolean true. If you are about to swap a value into an array position
that already contains that value, you have a duplicate.
On Jun 29, 4:52 am, Aakash Johari aakashj@gmail.com wrote:
Please read it again. Hashing would also help in the case of duplicates.
On Wed, Jun 29, 2011 at 9:16 AM, Gene gene.ress...@gmail.com wrote:
Your algorithm is good, but the first part doesn't help you because
duplicates are allowed.
Here is code that does what you say:
#include stdio.h
int main(void)
{
int a[] = { 6, 2, 4, 8, 7, 3, 5 };
int n = sizeof a / sizeof a[0];
int i, t, min, max, tmp;
min = max = a[0];
for (i = 1; i n; i++) {
if (a[i] min) min = a[i];
if (a[i] max) max = a[i];
}
if (min + n - 1 != max) {
printf(no\n);
return 1;
}
for (i = 0; i n; i++) {
while (a[i] != i + min) {
t = a[a[i] - min];
if (t == a[i]) {
printf(no\n);
return 1;
}
a[a[i] - min] = a[i];
a[i] = t;
}
}
for (i = 0; i n; i++)
printf(%d , a[i]);
printf(yes\n);
return 0;
}
On Jun 25, 11:22 pm, oppilas . jatka.oppimi...@gmail.com wrote:
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-ar.
..
--
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.-Hide quoted text -
- Show quoted text -
--
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.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
So, if the space doesnt matter. We can have an array A for hashing. So first we will find the minimum element in array suppose M. and in the other traversal of array, we will calculate for each element Ai in array Ai + (-M). So if it exceeds N then elements are not consecutive and other check that you will have to make is that it is already present in Array A. It goes in O(n). On Jun 26, 5:22 am, oppilas . jatka.oppimi...@gmail.com wrote: 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-ar... -- 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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: Sort - Consecutive Array in O(n)
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.
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.
[algogeeks] Re: sort the array
People should not just come over here , write one word and go .If you cannot explain you're logic with an example , means you haven't even tried the problem .You just want to boast you're adroit .In place merging of two sorted is not an easy problem . . On Jun 22, 9:48 pm, ankit mehta mehta.bond...@gmail.com wrote: Yes thats what I am saying that algorithm presented by Mr. Navneet wont work. On Jun 22, 9:40 pm, Apoorve Mohan apoorvemo...@gmail.com wrote: @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.
[algogeeks] Re: sort the array
@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.
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.
[algogeeks] Re: sort the array
In step 2 it should me m++ instead of n++ and similarly in step 3 n+ +. But still I dont think it will work if we carry out these iterations on this particular array. It will return , what I think: 1 2 3 5 10 4 8 12. Please correct me if I am wrong. On Jun 22, 7:50 pm, Navneet Gupta navneetn...@gmail.com wrote: 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
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.
[algogeeks] Re: sort the array
Yes thats what I am saying that algorithm presented by Mr. Navneet wont work. On Jun 22, 9:40 pm, Apoorve Mohan apoorvemo...@gmail.com wrote: @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.
Re: [algogeeks] Re: sort in minimum cost
Given the list, you would never want to decrement the last element as you
want it to be the maximum.
so either retain or remove the last element
Lets consider the Minimum cost among the sequence i to j as Cost[i..j]
So if you remove the element j, you add j to the cost
Cost[i..j] = Min{ Min(cost[i..j-1])+j, SortByDecremet(Cost(i..j))}
in SortByDecrement returns the total cost of decrementing the elements i to
j-1 so that they are not greater than element j(such that the list is
non-decreasing).
If we solve this equation recursively then I think we will get the minmum
cost.
I hope this can be represented in a better way/better equation.
Correct me if anything is not taken care of .
On Tue, Apr 26, 2011 at 3:58 PM, snehal jain learner@gmail.com wrote:
@above
you cant increment
On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@snehal jain
4 9 8 7 8
o/p 4 7 7 7 8
cost 3 by decrementing 9 n 8
Yes, now question is clear but your last example is incorrect.
4 9 8 7 8
o/p 4 8 8 8 8
cost 2 = decrementing (9 to 8) + incrementing (7 to 8)
--
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 in minimum cost
This seems longest increasing subsequence problem to me.. Thanks, Anurag On Mon, Apr 25, 2011 at 9:31 PM, snehal jain learner@gmail.com wrote: few eg input 4 7 12 3 1 output 4 7 12 cost: 4 by removing 3 n 1 eg 2 6 3 5 7 12 4 o/p 3 3 5 7 12 cost 7 by decrementing 6 by 3 and removing 4 eg 3 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 i hope its clear now.. On Mon, Apr 25, 2011 at 9:16 PM, hary rathor harry.rat...@gmail.comwrote: just tell me what is input and what will the output. atleast 3 example -- 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 in minimum cost
@snehal jain 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 Yes, now question is clear but your last example is incorrect. 4 9 8 7 8 o/p 4 8 8 8 8 cost 2 = decrementing (9 to 8) + incrementing (7 to 8) -- 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 in minimum cost
@above you cant increment On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal nav.coo...@gmail.comwrote: @snehal jain 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 Yes, now question is clear but your last example is incorrect. 4 9 8 7 8 o/p 4 8 8 8 8 cost 2 = decrementing (9 to 8) + incrementing (7 to 8) -- 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.
[algogeeks] Re: sort in minimum cost
I don't understand your example. If the input has only one 3, and the output has more than one, you have not sorted the elements. Do you mean alter the elements to make the array non-decreasing? Don On Apr 25, 4:21 am, snehal jain learner@gmail.com wrote: Given n elements, sort the elements. Here, only one operation is permitted decreaseValue.. Note that you cannot swap the values.. output should be a sorted list.. if input is 4 5 2 1 3 output is 3 3 3.. There can be many answers.. Give the optimum solution with minimum cost. where as cost is the sum of decreased amounts.. -- 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 in minimum cost
just tell me what is input and what will the output. atleast 3 example -- 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 in minimum cost
few eg input 4 7 12 3 1 output 4 7 12 cost: 4 by removing 3 n 1 eg 2 6 3 5 7 12 4 o/p 3 3 5 7 12 cost 7 by decrementing 6 by 3 and removing 4 eg 3 4 9 8 7 8 o/p 4 7 7 7 8 cost 3 by decrementing 9 n 8 i hope its clear now.. On Mon, Apr 25, 2011 at 9:16 PM, hary rathor harry.rat...@gmail.com wrote: just tell me what is input and what will the output. atleast 3 example -- 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.
[algogeeks] Re: Sort array with two subparts sorted
Why make this overcomplicated? There isn't a merge sort needed if two arrays were already sorted. It takes only O(n). Each time, you compare the leading elements and remove the smaller one and store it in a new array. On Apr 12, 6:33 pm, Carl Barton odysseus.ulys...@gmail.com wrote: Very interesting link! As we only need to perform one merge we should be able to modify it to run in O(n) time? In a similar style as a strand sort? On 12 April 2011 22:55, hary rathor harry.rat...@gmail.com wrote: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html take a glance on this merge sort this is Inplace and also stable -- 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.
[algogeeks] Re: Sort array with two subparts sorted
@ligerdave.. actually.. the problem is, O(n) is correct, but, this will again space dependent where it is again O(n).. so.. it has to be done in constant space.. no additional space.. so.. just swapping is allowed.. what's the best time complexity for this? -- 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.
[algogeeks] Re: Sort array with two subparts sorted
Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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 array with two subparts sorted
That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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 array with two subparts sorted
But Vaibhav's solution I think is O(n^2). For example, when input is 101 102 103 104 1 2 3 4 We first swap 1 and 101 and then bubble 101 to the end of the subarray 2 3 4 . This bubbling we must repeat after each swap. This results in n/2 + n/2-1 + n/2-2 + .. comparisons, which is O(n^2). Please correct me if I am wrong. Can this be solved in better than O(n^2) with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 8:43 PM, Carl Barton odysseus.ulys...@gmail.comwrote: That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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 array with two subparts sorted
Okay, forgetting the information that two parts are sorted and treating it as any other array, we can sort in O(nlogn) using, say, heapsort. Is O(n) possible with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 9:25 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote: But Vaibhav's solution I think is O(n^2). For example, when input is 101 102 103 104 1 2 3 4 We first swap 1 and 101 and then bubble 101 to the end of the subarray 2 3 4 . This bubbling we must repeat after each swap. This results in n/2 + n/2-1 + n/2-2 + .. comparisons, which is O(n^2). Please correct me if I am wrong. Can this be solved in better than O(n^2) with constant space ? Thanks, Balaji. On Tue, Apr 12, 2011 at 8:43 PM, Carl Barton odysseus.ulys...@gmail.comwrote: That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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.
[algogeeks] Re: Sort array with two subparts sorted
say we hav array {101,102,103,104(ptr1),1,2,3,4(ptr2)}
1.take end of 1 st array in ptr1end of 2nd array in ptr2
2.IF (ptr1ptr2)
bubble up ptr1 to ptr2;
ptr2--
ptr1--
ELSE
ptr2--;
1.compare last element of both arrays ie 104 4 since 1044
bubble up 104 to end since it will be greater than whole 2 nd array
so {101,102,103(ptr1),1,2,3,4(ptr2),104}
moving on
ex 2 : {1,3,5,7(ptr1),2,4,6,8(ptr2)}
78 so ptr2-- {1,3,5,7(pr1),2,4,6(ptr2),
8} {1,3,5(ptr1),2,4,6(ptr2),7,8} moving on..
--
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 array with two subparts sorted
since we are bubbling up, it's again is a O(n^2).
Is there anything possible like O(n) in constant space. I tried on swapping
values but mees it somewhere... here are intermediate steps in my approach.
1, 5, 7, 9, 11, 2, 3, 8, 9, 21
1, 2, 7, 9, 11, *5*, 3, 8, 9, 21
1, 2, 3, 9, 11, *5, 7*, 8, 9, 21
1, 2, 3, 5, 11, 9, 7, 8, 9, 21
1, 2, 3, 5, 7, 9, 11, 8, 9, 21
1, 2, 3, 5, 7, 8, 11, 9, 9, 21
1, 2, 3, 5, 7, 8, 9, 11, 9, 21
1, 2, 3, 5, 7, 8, 9, 9, 11, 21
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Tue, Apr 12, 2011 at 10:23 PM, powerideas
arpitbhatnagarm...@gmail.comwrote:
say we hav array {101,102,103,104(ptr1),1,2,3,4(ptr2)}
1.take end of 1 st array in ptr1end of 2nd array in ptr2
2.IF (ptr1ptr2)
bubble up ptr1 to ptr2;
ptr2--
ptr1--
ELSE
ptr2--;
1.compare last element of both arrays ie 104 4 since 1044
bubble up 104 to end since it will be greater than whole 2 nd array
so {101,102,103(ptr1),1,2,3,4(ptr2),104}
moving on
ex 2 : {1,3,5,7(ptr1),2,4,6,8(ptr2)}
78 so ptr2-- {1,3,5,7(pr1),2,4,6(ptr2),
8} {1,3,5(ptr1),2,4,6(ptr2),7,8} moving on..
--
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 array with two subparts sorted
u can use Quick sort which is inplace -- 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 array with two subparts sorted
u can use Quick Sort which take O(nlogn) and it is also inplace -- 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 array with two subparts sorted
quick sort is worst case O(n^2)
On 12 April 2011 18:17, Akash Agrawal akash.agrawa...@gmail.com wrote:
since we are bubbling up, it's again is a O(n^2).
Is there anything possible like O(n) in constant space. I tried on swapping
values but mees it somewhere... here are intermediate steps in my approach.
1, 5, 7, 9, 11, 2, 3, 8, 9, 21
1, 2, 7, 9, 11, *5*, 3, 8, 9, 21
1, 2, 3, 9, 11, *5, 7*, 8, 9, 21
1, 2, 3, 5, 11, 9, 7, 8, 9, 21
1, 2, 3, 5, 7, 9, 11, 8, 9, 21
1, 2, 3, 5, 7, 8, 11, 9, 9, 21
1, 2, 3, 5, 7, 8, 9, 11, 9, 21
1, 2, 3, 5, 7, 8, 9, 9, 11, 21
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Tue, Apr 12, 2011 at 10:23 PM, powerideas arpitbhatnagarm...@gmail.com
wrote:
say we hav array {101,102,103,104(ptr1),1,2,3,4(ptr2)}
1.take end of 1 st array in ptr1end of 2nd array in ptr2
2.IF (ptr1ptr2)
bubble up ptr1 to ptr2;
ptr2--
ptr1--
ELSE
ptr2--;
1.compare last element of both arrays ie 104 4 since 1044
bubble up 104 to end since it will be greater than whole 2 nd array
so {101,102,103(ptr1),1,2,3,4(ptr2),104}
moving on
ex 2 : {1,3,5,7(ptr1),2,4,6,8(ptr2)}
78 so ptr2-- {1,3,5,7(pr1),2,4,6(ptr2),
8} {1,3,5(ptr1),2,4,6(ptr2),7,8} moving on..
--
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.
