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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.