0

I want to find count of elements in an array which have the following two conditions:

  1. 1 <= i < j <= n
  2. a[i] > a[j]

Im using the following code but i need a faster one any advice?

for(int i=0; i<n; i++){
    for (int j=i+1; j<n; ++j){
        if (a[j] < a[i])
            ans++;
    }
}
walnut
  • 21,629
  • 4
  • 23
  • 59
Hamidreza Hanifi
  • 17
  • 8
  • 1
    One piece of advice; regardless of what algorithm you use, test a build of your code with optimizations *enabled* (aka a Release build). Don't test a default Debug build. Compiler optimizations can make a *big* performance difference. – Jesper Juhl Jan 11 '20 at 16:30
  • When you say "*faster one*" do you mean faster asymptotically for large array sizes or what array size are we talking about? – walnut Jan 11 '20 at 16:32
  • @walnut yea i mean asymptotically for large array sizes – Hamidreza Hanifi Jan 11 '20 at 16:37
  • @JesperJuhl i keep that in mind thanks for the tip :) – Hamidreza Hanifi Jan 11 '20 at 16:38
  • 1
    Does this answer your question? [Find the number of unordered pair in an array](https://stackoverflow.com/questions/26702051/find-the-number-of-unordered-pair-in-an-array) or [Counting inversions in an array](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array) – walnut Jan 11 '20 at 16:39
  • @walnut yea thats it thanks for ur help :) – Hamidreza Hanifi Jan 11 '20 at 17:57

1 Answers1

3

What you're trying to do is called inversion count. Asymptotically speaking, the complexity of your current algorithm is O(n^2). You can do it in O(nlogn) time using a merge sort based divide and conquer approach. Read more about it here.

Ajay Dabas
  • 1,404
  • 1
  • 5
  • 15