@ross
i can do it in O(n) time using an extra array of the same size as the given
array
first sort both the even indexed terms and odd indexed terms by modifying
quick sort...it can be done in one traversal.....
and then using extra array and then move the even indexed terms followed by
odd indexed terms....
i think it should work......
if anyone have the idea that can reduce the space required then please share
!!
On Fri, May 27, 2011 at 1:29 PM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
> how large n will be...O(n) can't grow more than O(nlogn)....so in any
> case the complexity is going to be O(nlogn)..so i dnt see any point of
> bringing our any modification of mergersort...even if u think so,
> provide a concrete algo
>
> On 5/28/11, LALIT SHARMA <lks.ru...@gmail.com> wrote:
> > It will give correct answer ,
> > but instead of doing manipulation after taking input.
> > as it would take some O(n) time. if n would be large , we would incur
> > this extra cost .
> >
> > we should change the termination condition of merge-sort function and
> > modify the merge function of merge sort ..to reach our objective .
> >
> > correct me , if i am wrong ...
> >
> > On Sat, May 28, 2011 at 1:40 AM, Piyush Sinha <ecstasy.piy...@gmail.com>
> > wrote:
> >> main()
> >> {
> >> int a[100];
> >> int i,j,N;
> >> printf("enter the number of elements: ");
> >> scanf("%d",&N);
> >> for(i=0;i<N;i++)
> >> scanf("%d",a[i]);
> >> if(N%2) j = N/2+1;
> >> else j = N/2;
> >> i =1;
> >> while(j<N)
> >> {
> >> swap(&a[i],&a[j]);
> >> i+=2;
> >> j+=2;
> >> }
> >> if(N%2){
> >> inv_mergesort(a,0,N/2);//sort the array in descending order
> >> mergesort(a,N/2+1,N-1);
> >> }
> >> else{
> >> inv_mergesort(a,0,N/2-1);//sort the array in descending order
> >> mergesort(a,N/2,N-1);
> >> }
> >>
> >> for(i=0;i<N;i++)
> >> printf("%d",a[i]);
> >> }
> >>
> >> I hope the code doesn't contain any bugs...:P :P
> >>
> >> On 5/28/11, srajan dongre <srajan.don...@gmail.com> wrote:
> >>> wat about insertion sort (with some limited conditions obviously ) ??
> >>>
> >>> On Sat, May 28, 2011 at 12:56 AM, Piyush Sinha
> >>> <ecstasy.piy...@gmail.com>wrote:
> >>>
> >>>> will it be given that the number of elements is always even??
> >>>>
> >>>> On 5/28/11, ross <jagadish1...@gmail.com> wrote:
> >>>> > Hi all,
> >>>> >
> >>>> > Sort all elements in odd indices of an array in ascending order and
> >>>> > even indices in descending order.
> >>>> > Finally, rearrange so that all even indexed elements come first.
> >>>> >
> >>>> > eg:
> >>>> >
> >>>> > input – 7 2 6 4 8 3 1
> >>>> >
> >>>> > even indexed : 7 6 8 1 => sort 8 7 6 1
> >>>> > odd indexed: 2 4 3 => sort 2 3 4
> >>>> >
> >>>> > output – 8 7 6 1 2 3 4
> >>>> >
> >>>> > What could be the best algo to solve it?
> >>>> > Is it possible to arrive at the output using only O(1) 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.
> >>>> >
> >>>> >
> >>>>
> >>>>
> >>>> --
> >>>> *Piyush Sinha*
> >>>> *IIIT, Allahabad*
> >>>> *+91-8792136657*
> >>>> *+91-7483122727*
> >>>> *https://www.facebook.com/profile.php?id=100000655377926 *
> >>>>
> >>>> --
> >>>> You received this message because you are subscribed to the Google
> >>>> Groups
> >>>> "Algorithm Geeks" group.
> >>>> To post to this group, send email to algogeeks@googlegroups.com.
> >>>> To unsubscribe from this group, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com.
> >>>> For more options, visit this group at
> >>>> http://groups.google.com/group/algogeeks?hl=en.
> >>>>
> >>>>
> >>>
> >>>
> >>> --
> >>> ------
> >>>
> >>> Srajan Dongre
> >>> ||nd year CSI (dual degree)
> >>> Indian Institute of Technology , Roorkee
> >>> Uttrakhand , India
> >>> pin code--247667
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from 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=100000655377926 *
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >>
> >
> >
> >
> > --
> > Lalit Kishore Sharma,
> > IIIT Allahabad (Amethi Capmus),
> > 6th Sem.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from 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=100000655377926 *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.
