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.
