check dis link
http://www.1771.in/how-many-comparisons-are-needed-in-worst-case-if-we-have-to-sort-7-numbers-each-of-4-digit.html
On Tue, Aug 7, 2012 at 9:38 PM, Sambhavna Singh wrote:
> Its radix sort..
>
>
> On Fri, Aug 3, 2012 at 4:39 PM, Navin Gupta wrote:
>
>> I think the no. of comparison
Its radix sort..
On Fri, Aug 3, 2012 at 4:39 PM, Navin Gupta 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 201
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 e
On Tuesday, 13 July 2010 17:32:43 UTC-7, Gene wrote:
>
> On Jul 13, 2:46 pm, Devendra Pratap Singh
> wrote:
> > @gene
> >
> > thanx for the working code
> >
> > but can u explain its working more clearly
> >
> > On Jul 13, 11:21 pm, Gene wrote:
> >
> >
> >
> > > On Jul 10, 5:18 pm,
@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 wrote:
> @praveen : k way merge would require extra
@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 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
>
>
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
@ lucifer: thank you !
On Sun, Jan 22, 2012 at 4:12 PM, Lucifer 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
@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
@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:
@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...*/
@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 a
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
"
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 discussi
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
@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 po
@pankajsingh, did u observe the array in the 4th step?
I think it will be like this
1 2 3 4 9
5 8 18 25 50
6 7 22 45 55
The second column is not sorted. You need to sort not only the rows, but
also the columns accordingly. I think it will become more complex.
On Wed, Jan 11, 2012 at 5:51 PM, pa
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
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
@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/
@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
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 wro
@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
@atul..
Missed ur previous post by a couple of mins..
Nyways it seems u got it .. :)..
On Jan 11, 10:44 pm, Lucifer 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
@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 alway
correction : /*set min at position A[i+1][0] after heafiying */
On Wed, Jan 11, 2012 at 11:07 PM, atul anand 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 ) .
>
>
@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 , s
@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 bin
@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 se
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
@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
Think about the cost of picking the minimum. It's not O(1).
On Jan 11, 3:34 am, Sanjay Rajpal wrote:
> 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).
>
>
@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 node
@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 wrote:
> @Shady : you would definitely need two index variables for each array I
> feel.
-
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
@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
algo
@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...(Recu
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 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
@shady..
Look out for in-place merge sort...
On Jan 11, 4:23 pm, shady 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 wrote:
> > @ all k-way people : I dont get it
@shady :
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=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 wrote:
> any idea on how to merge two sorted arrays of size m and size n in O(m+n)
>
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 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 t
@ 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 sort
@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
@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 wrote:
> @Lucifer : I came up with a similar algorithm as yours but I dont
> u
@correction..
for ( int row = 0; row < *M*; ++row)
On Jan 11, 1:56 pm, Lucifer 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
@correction:
/*
basically either go down or go
*right* in case adjustment is required...
*/
On Jan 11, 1:56 pm, Lucifer 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 b
@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
Bitonic sort
On Aug 31, 11:26 am, bharatkumar bagana
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 Gupt
@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 wrote:
> @dave, ur converting array values i
@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 wro
@Arun: Look up "Radix sort" and then read the comments in the code.
Dave
On Aug 3, 4:23 am, Arun Vishwanathan 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 wrote:
> > @Dave,
> > Can you
@Payel: Look up "Radix sort" and then read the comments in the code.
Dave
On Aug 2, 11:51 pm, payel roy wrote:
> @Dave,
> Can you please explain the algo? It's getting very difficult to understand
> the code ..
>
> On 3 August 2011 01:14, Dave wrote:
>
>
>
> > @Pankaj: Assuming generously that
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 wrote:
> @Dave,
> Can you please explain the algo? It's getting very difficult to understand
> the code ..
>
>
> On 3 August 2011 01:14, Dave wrote:
>
>> @Pank
@Dave,
Can you please explain the algo? It's getting very difficult to understand
the code ..
On 3 August 2011 01:14, Dave 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 t
@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;
// initia
absolutely correct dudethat was the way i read in clrs in radix
sort chap
On Aug 2, 4:50 pm, Harshit Kapoor 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 h
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(n<1)
return 0;
int min=a[0];
int max=a[0];
int i=0;
for(i=1;imax)
max=a[i];
}
if(max-min+1!=n)
return 0;
for(i=0;i wrote:
>
> a) F
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 conse
@sunny I dont understand the final checking part..Can u pls explain.
On Sun, Jul 3, 2011 at 5:48 AM, Gene 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 wrote:
> > can
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 wrote:
> can we not use count sort because of O(n) .?
--
You received this message because you are subscribed to the Google Groups
"Algo
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.co
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
can't we directly hash the values at a[i] % N, if value is Negative hash to
(A[i]%N) + N
if two values hash to same places -Not consecutive
But still we can have a problem like
N = 2 and a[] = {1,4}
because of hash value of values in the array may be consecutive but not the
actual values
so af
Please read it again. Hashing would also help in the case of duplicates.
On Wed, Jun 29, 2011 at 9:16 AM, Gene 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
>
> int main(void)
> {
> i
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
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;
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
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
@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-determi
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
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, 20
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
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; ihttp://groups.google.com/group/algogeeks?hl=en.
@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 wrote:
> Missed that... also, my method seems to work only if num
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
a
@Adarsh
fails on this
a[] = {2,2,2,6,6,6}
On Sat, Jun 25, 2011 at 10:54 AM, Adarsh wrote:
> int n = A.size();
> for (int i=0; itotal += A[i];
> findMinMax(A[1...n]);
>
> int mean = (max+min)/2;
> if ((total - n*mean) == 0)
>printf("consecutive\n");
> else
>printf("not consecutive\n")
int n = A.size();
for (int i=0; ihttp://groups.google.com/group/algogeeks?hl=en.
Gene is correct :)
Counter example
{1, 2, 2, 5, 5}
See method 3 here http://geeksforgeeks.org/?p=11516
On 6/25/11, Gene 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 differe
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
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)
re
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 wrote:
> Given an array, A, find if all elements in the sorted version of A are
> consecutive in les
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 wrote:
>
Yes thats what I am saying that algorithm presented by Mr. Navneet
wont work.
On Jun 22, 9:40 pm, Apoorve Mohan 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 ema
@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.
Fo
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]
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 wrote:
> Let
On Wed, Jun 22, 2011 at 8:38 PM, oppilas . wrote:
>
>
> On Wed, Jun 22, 2011 at 8:20 PM, Navneet Gupta 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
On Wed, Jun 22, 2011 at 8:20 PM, Navneet Gupta 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
>
*I think it should be increment
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
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 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
@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!
>
>
This seems longest increasing subsequence problem to me..
Thanks,
Anurag
On Mon, Apr 25, 2011 at 9:31 PM, snehal jain 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
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(c
@above
you cant increment
On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal wrote:
> @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) + in
@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
"Al
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 wrote:
> just tell me
>
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+
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 wrote:
> Given n elements, sort the elements. Here, only one ope
@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 becaus
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 wrote:
> Very interesting link!
>
> As we on
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 wrote:
>
> http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
>
>
> take a glance on this
1 - 100 of 175 matches
Mail list logo
