important_dsa_problems/Count_Inversions.cpp at main · arinyadav/important_dsa_problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
O(n2) -- take two loops and count how many of unsorted pairs are there in which do not follow ascending rule

O(nlogn) -- use merge sort concept

  // CODE STARTED

 long long merge(long long arr[], long long low, long long mid,  long long high){
  long long ans=0;
  long long  len1= mid-low+1;
  long long  len2= high-mid;
  long  arr1[len1];
  long  arr2[len2];


        for(int i=0;i<len1;i++){


            arr1[i]= arr[i+low];

        }


         for(int i=0;i<len2;i++){


            arr2[i]= arr[i+mid+1];

        }


        long long  i=0, j=0,k=low;


        while(i<len1&&j<len2){


            if(arr1[i]<=arr2[j]){


                arr[k]= arr1[i];

                i++;

                k++;


            }else {


                arr[k]= arr2[j];


                ans+=len1-i;

                k++;

                j++;


            }

        }
  while(i<len1){
          arr[k]= arr1[i];

            i++;

            k++;

        }
  while(j<len2){
           arr[k]= arr2[j];

            j++;

            k++;

       }
  return ans;
    }
long long mergesort(long long arr[], long long low, long long high){
      if(low>=high)
       return 0;

        }
      long long ans=0;
      long long mid= low+ (high-low)/2;
      ans+=mergesort(arr, low, mid);
      ans+=mergesort(arr, mid+1, high);
      ans+= merge(arr, low,mid, high);
      return ans;

    }
    long long int inversionCount(long long arr[], long long N)

    {
    return mergesort(arr, 0, N-1);

    }