@Raj: give a sample test case
On Sep 14, 11:00 am, "Shiv ..." <shivsinha2...@gmail.com> wrote:
> 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
> <wladimir...@gmail.com>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
> > <aryansmit3...@gmail.com>wrote:
>
> >> linear decreasing sub sequence problem
>
> >> On Mon, Sep 13, 2010 at 9:10 PM, Raj N <rajn...@gmail.com> 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 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.
>
> >> --
> >> 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 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.
--
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.
