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.
