good one shifting array is the solution but i want to do it without shifting, is there a solution!!!
Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Thu, Jul 15, 2010 at 4:26 AM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote: > try merging this array > [{5,9,10},{3,6,7,9}]... > > On Wed, Jul 14, 2010 at 9:30 AM, Ashish Goel <ashg...@gmail.com> wrote: > >> >> >> int dstart = -1; >> int dend = -1; >> int istart=-1; int iend = -1; >> bool decreasing = false; >> for (int i=1;i<n;i++) >> { >> if (a[i] >=a[i-1]) >> { if (decreasing) >> { >> dend =i-1; istart=i; >> reverse (a, dstart, dend); >> merge(a,0,dstart-1, dstart, dend); ///merge 0, dstart-1 array with >> array starting at dstart ending at dend >> decreasing = false; >> } >> // else continue; >> } >> if (!decreasing) //first decreasing >> { >> decreasing = true; >> dstart = i; >> iend=i-1; >> merge(a,0, istart-1, istart, iend); >> } >> } >> >> the number of comparison in each merge would be max O(m+n) where m is int >> number of elements in first list and n in second. so if the merge is >> happening k times the order would become O(k*(m+n)) types >> >> >> merge will do the merging from bottom so that shift downs are not needed. >> >> int r1= end1; >> int r2=end2; >> //for every write position, only 1 comparison is done >> while (r2>=start1) >> { >> if (a[r1]>a[r2]) >> { >> swap(a[r1],a[r2]); >> r2--;//r2 is also write position >> } >> else >> { >> r1--; >> } >> if (r1==r2) r1--; >> } >> >> >> so fr >> 5,10,9,14,13,12,17,16,21,20 >> >> >> what would be the order? >> >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> On Tue, Jul 13, 2010 at 6:00 AM, Gene <gene.ress...@gmail.com> wrote: >> >>> On Jul 12, 10:48 am, Tech Id <tech.login....@gmail.com> wrote: >>> > This is a good solution. >>> > >>> > Reversing the arrays will be O(n) >>> > Then merging will be O(n) too. >>> > >>> > In place merge is something like this. >>> > Have two indices as start1 and start2 >>> > start1 points to beginning of mini-sorted portion1 >>> > start2 points to beginning of mini-sorted portion2 >>> > >>> > Increase both start1 and start2 and swap when necessary. >>> > adjust start1 and start2 accordingly. >>> > >>> > Do the same for other mini-sorted arrays. >>> > >>> > So the complexity of this is mO(n) where m is the number of mini >>> > arrays. >>> > For m=1, it becomes O(n^2) as expected for a normal sort! >>> >>> Correct algorithms for in-place merge are much harder than what you're >>> describing here. Think it through carefully, and you'll see this. >>> >>> And don't forget that if you are merging K lists, you need at least K >>> log K comparisons to decide the merge order at each step. So if the >>> lists being merged have about N items each, the cost of merging is O(N >>> K log K) . In other words, the "K" in K-tonic makes a difference. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<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 algoge...@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.