fork(1) download
copy 
  1. #include "iostream"
  2.  
  3. using namespace std;
  4.  
  5. int total_inversions = 0;
  6. int count_inversion_merge(int array[], int mid, int n) {
  7.     int i = 0, j = mid, k, inversion = 0;
  8.     int b[n];
  9.     for (k = 0; k < n; k++) {
  10.         if (j == n || (i < mid && array[i] < array[j])) {
  11.             b[k] = array[i];
  12.             i++;
  13.         } else {
  14.             b[k] = array[j];
  15.             j++;
  16.             inversion+=mid-i;
  17.         }
  18.     }
  19.     return inversion;
  20. }
  21.  
  22.  
  23. int count_inversion(int a[], int n) {
  24.     if (n <= 1) {
  25.         return 0;
  26.     }
  27.     count_inversion(a, n / 2);
  28.     count_inversion(a + (n / 2), n - n / 2);
  29.     total_inversions+=count_inversion_merge(a, n / 2, n);
  30.     return total_inversions;
  31.  
  32. }
  33. int main() {
  34.  
  35. //    int a[] ={ 2, 4, 1, 3, 5 };
  36.     int a[] ={ 1, 20, 6, 4, 5 };
  37.     cout << count_inversion(a, 5);
  38.  
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/raKD7T
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!