Hi Jagadish, Anurag's algo has O(n) for pre-processing. After that any sorting algorithm will be applied there also.
On Wed, Jun 23, 2010 at 7:22 PM, Jagadish M <[email protected]> wrote: > >Why not just change the definition of when one number is bigger than > another > >and do normal sort ? > >I guess that is better and simpler. > > Normal sort takes O(n log n), while Anurag's algo is O(n). > > > Regards, > Jagadish > http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> > > > > > > > On Jun 20, 2:18 pm, Rohit Saraf <[email protected]> wrote: > > Why not just change the definition of when one number is bigger than > another > > and do normal sort ? > > I guess that is better and simpler. > > -------------------------------------------------- > > Rohit Saraf > > Second Year Undergraduate, > > Dept. of Computer Science and Engineering > > IIT > > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > > On Sun, Jun 20, 2010 at 7:52 AM, Anurag Sharma <[email protected] > >wrote: > > > > > > > > > Keep 2 pointers 'start' and 'end' and make them point to start and > > > beginning of the array. > > > > > Now keep decresing *end* pointer until an odd element is found > > > Keep increasing the *start* pointer until an even element is found > > > swap the elements at start and end > > > Continue the above 3 steps till start<end > > > > > Now the start/end points to a border element which divides the array in > 2 > > > parts, 1st have having all odd numbers and 2nd half with all even > numbers. > > > > > Now use any inplace sorting algorithm to sort in descending order the > > > portion containing all odd numbers and in increasing order the portion > > > containing all even numbers. > > > Hope its clear. > > > > > Anurag Sharma > > > > > On Sun, Jun 20, 2010 at 2:15 AM, vijay <[email protected]> wrote: > > > > >> There is an array of odd and even numbers. Now, sort them in such a > > >> way that the top portion of the array contains odd numbers, bottom > > >> portion contains even numbers. The odd numbers are to be sorted in > > >> descending order and the even numbers in ascending order. You are not > > >> allowed to use any extra array and it has to use a conventional > > >> sorting mechanism and should not do any pre or post processing > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]<algogeeks%[email protected]> > <algogeeks%2bunsubscr...@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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]<algogeeks%[email protected]> > <algogeeks%2bunsubscr...@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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards Bhanu Mobile +91 9886738496 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
