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