@sunny: got dat...
On 7/22/11, saurabh singh <saurab...@gmail.com> wrote:
> So many why's..:)
> I was just trying to explain the queries about the divide and conquer asked
> above.+1 to u sunny.
>
> On Fri, Jul 22, 2011 at 1:26 PM, sunny agrawal
> <sunny816.i...@gmail.com>wrote:
>
>> Yes thats true,
>> but that will take O(n) extra space in merging step, isn't it ?
>> and if we have to use O(n) space why dont just use O(n) algorithm !!
>>
>> On Fri, Jul 22, 2011 at 1:18 PM, saurabh singh <saurab...@gmail.com>wrote:
>>
>>> For people who like the generic way,its merge sort only difference is
>>> where comp(a,b) returns true when a%2=1&&a%2=0.
>>> Rest its same.
>>>
>>> On Fri, Jul 22, 2011 at 1:12 PM, sunny agrawal
>>> <sunny816.i...@gmail.com>wrote:
>>>
>>>> Divide and Conquer Algorithm : Just like merge Sort of Quick
>>>> sort.......we just need to modify the merge step of merge sort or
>>>> Partition
>>>> step of Quick sort
>>>>
>>>> lets call our this method Arrange();
>>>> //just as merge step takes two sorted arrays and make one completely
>>>> sorted one
>>>> it takes 2 arrays which are already in the required form (first even nos
>>>> then odds)
>>>>
>>>> then these two arrays will look like
>>>> EVEN1 ODD1 EVEN2 ODD2
>>>> and we need to arrange them as
>>>> EVEN1 EVEN2 ODD1 ODD2
>>>>
>>>> so we just need to swap middle part or rotate middle part that will take
>>>> O(n) time in worst case and depth of recursion will be O(lgn) hence
>>>> O(nlgn)
>>>>
>>>> recursive calls will end when size of subarray is less than or equal to
>>>> 2
>>>> i leave it to you how to handle base cases of recursion :) :D
>>>>
>>>> Ex. 1,2,3,4
>>>>
>>>> will call to (1,2), (3,4)
>>>> after solving both the basecases
>>>> arrays will be (2,1) (4,3)
>>>> now arrange function will just swap the ODD1 and EVEN2
>>>> result will be (2,4,1,3)
>>>>
>>>> On Fri, Jul 22, 2011 at 12:36 PM, Puneet Gautam <puneet.nsi...@gmail.com
>>>> > wrote:
>>>>
>>>>> @sunny: how do u do it by "Divide n conquer "...can u provide the
>>>>> algo...?
>>>>>
>>>>>
>>>>> On 7/22/11, UMESH KUMAR <kumar.umesh...@gmail.com> wrote:
>>>>> > Anybody try for maintain the stable of elements in O(n) as like
>>>>> >
>>>>> > Input is :{1,2,3,4,5,6,7}
>>>>> > then Output should be
>>>>> > (2,4,6,1,3,5,7)
>>>>> > not..........
>>>>> >
>>>>> > {2,4,6,1,5,3,7} base on above discussion ..................
>>>>> >
>>>>> > --
>>>>> > You received this message because you are subscribed to the Google
>>>>> Groups
>>>>> > "Algorithm Geeks" group.
>>>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>>>> > To unsubscribe from 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.
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> Saurabh Singh
>>> B.Tech (Computer Science)
>>> 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.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> 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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
