@Anand, @Abhishek
Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in
O(n) time. We are dividing and calling bitonicmerge() on two parts
recursively. So this should run in O(n log n) time complexity as
shown below
T(n) = n/2 + 2T(n/2) = n/2
I think this will work.
# include stdio.h
void my_print(int *,int);
void swap(int a , intb)
{
a = a + b;
b = a - b;
a = a - b;
}
void sort(int* array, int SIZE, int i, int j)
{
while(ij)
{
my_print(array,SIZE);
if(array[i] = array[j])
Is not ur code is running in o(n^2) complexity
You have used two while loop ...
plzz eleborate if i m wrong .
On Jul 12, 11:00 am, Amit Mittal amit.mitt...@gmail.com wrote:
I think this will work.
# include stdio.h
void my_print(int *,int);
void swap(int a , intb)
{
a = a + b;
@souravsain
for input {10,20,30,40,50,23,27};
ur output is coming 10, 20, 23, 27, 40, 30, 50,
which not SORTED array.
On Jul 10, 6:19 pm, souravsain souravs...@gmail.com wrote:
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look
@problem owner
Have you posted the correct question? Because this does
not seems like a trivial question which someone can ask in the middle
of an interview. I found a similar question while googling. It reads:
There are two sorted arrays A1 and A2. Array A1 is full where
@problem owner
Have you posted the correct question? Because this does
not seems like a trivial question which someone can ask in the middle
of an interview. I found a similar question while googling. It reads:
There are two sorted arrays A1 and A2. Array A1 is full where
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look at http://codepad.org/iMBTwAL7
Appriciate the effort taken by you to analyze the solution and do let
me know if you still do not agree with the code.
Regards,
Sourav
On Jul 8, 9:03 pm,
@Jitendra
Sorry for the previous post. There is a problem in my approach. I
overlooked that.
Working on it.. :(
On Jul 8, 9:03 pm, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1 for
further comparison
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google
@all
Please find my O(n) time and O(1) space implementation for this
problem.
Summary of approach: let i be start for first sorted part and j be
start of next sorted part. move i as long as a[i] is less than a[j] as
that means things are sorted.
if a[i] a[j], swap them and increment i.
I believe a merge sort requires O(n) space complexity. Is stack spce
counted towards space complexity? If not, I imagine you could write a
merge sort recursively, so that the explict space usage has O(1)
complexity.
On Jul 2, 2:37 pm, Abhishek Sharma jkabhishe...@gmail.com wrote:
I think its
@Anand
Also you cannot conclude that k will be middle. There is no mention of
half. Its that only kn. So you can also have something lke
[9,1,2,3,4,5,6] = [9] [1,2,3,4,5,6]
[8,9,10,11,3,4,7,15,17] = [8,9,10,11] [3,4,7,15,17]
and so on
Sourav
On Jul 3, 1:32 am, Anand anandut2...@gmail.com
@Anand , thanx for info , but does the question asked requires so
much ?
I felt , you have two sorted sub arrays so simply merging it (of merge
sort fame ! ) would solve it , isn't it ?
On Jul 3, 9:24 am, ankur bhardwaj ankibha...@gmail.com wrote:
@anand: this code will not work when n is not
@Anand
Please explain how you concluded that the array will first
continuously increase and then continuously decrease? Why can it not
be 2 continuous increase like [1,2,3,4,5,3,4,8] where [1,2,3,4,5] and
[3,4,8] are a[1] to a[k] and a[k+1] to a[N] respectively? Whill your
method work still?
@souravsain:
Given an array of n elements and an integer k where kn. Elemnts
{a[0].a[k] and a[k+1].a[n] are already sorted.
As per the question a{0} to a{k} is sorted and a{K+1} to a{n} is sorted
so we look at the sequence in a{0} to a{k} and {n} to a{k+1} it makes a
bitonic sequence.
15 matches
Mail list logo
