A pseudo code-
====
int n; //= number of inputs.
cin>>*a; // the inputs.
int ** invArr;
*inVArr[n-1] = NULL;
//initialise all the elemnts with Null to be safe.
for(int i = n-1; i > =0; i--) {
for (int j = i; j < n; j++ )
{
if(a[i] == a[j]) {
*invArr[i] = *invArr[j];
break;
}
if( a[i] > a[j]) {
invArr[i][0] = a[j];
*invArr[i] + 1 = *invArr[j];
break;
}
} //inner for
}//outer for
//print invArr;
==========
Please note the worst case would still be O(n^2). But I think average will
be significantly improved. (I will be happy if someone can do these
calculations. :)) )
And this is such a pseudo code. I will be grateful if someone can make this
run-able.
-thanks.
On Tue, Sep 14, 2010 at 2:34 AM, Wladimir Tavares <[email protected]>wrote:
> My two cents
>
> If you were asked in O(n log n)
>
> you have to modified the merge sort algorithm for count the number of
> inversion!
>
>
>
> Wladimir Araujo Tavares
> http://www.si.ufc.br/~wladimir <http://www.si.ufc.br/%7Ewladimir/>
> "Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos."
>
>
>
>
>
> On Mon, Sep 13, 2010 at 1:05 PM, sharad kumar <[email protected]>wrote:
>
>> linear decreasing sub sequence problem
>>
>>
>>
>> On Mon, Sep 13, 2010 at 9:10 PM, Raj N <[email protected]> wrote:
>>
>>> Given an array of n integers find all the inversion pairs in O(n)
>>> Inversion pair is one where a[i]>a[j], i<j
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> yezhu malai vaasa venkataramana Govinda Govinda
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
