There is a function for counting inversions in the array, which requires O (n2) time:

static void Inverses(int[] A, ref int count) { count = 0; for(int i = 0; i < A.Length - 1; i++) { for (int j = i + 1; j < A.Length; j++) { if( A[i] > A[j] ) count++; } } }

There is also a function of sorting the array with the divide and conquer approach, which requires O (n * log (n)) time:

  static Int32[] Merge_Sort(Int32[] massive) { if (massive.Length == 1) return massive; Int32 mid_point = massive.Length / 2; return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray())); } static Int32[] Merge(Int32[] mass1, Int32[] mass2) { Int32 a = 0, b = 0; Int32[] merged = new int[mass1.Length + mass2.Length]; for (Int32 i = 0; i < mass1.Length + mass2.Length; i++) { if (b < mass2.Length && a < mass1.Length) if (mass1[a] > mass2[b]) merged[i] = mass2[b++]; else //if int go for merged[i] = mass1[a++]; else if (b < mass2.Length) merged[i] = mass2[b++]; else merged[i] = mass1[a++]; } return merged; }

It is necessary to implement an algorithm for counting inversions in an array with the divide-and-conquer approach, which would require O (n * log (n)) time.

Unfortunately, it is quite hard for me to understand recursion, when the first method calls another method, and the other calls the first provided.

2 answers 2

You first need to deal with merge sorting, namely, to understand the idea of ​​the algorithm, and then deal with inversion.

I will say briefly: we divide the array into two parts, each of these parts, in turn, is also divided into two parts, etc., until our parts consist of one element. After splitting, we merge the parts into one in pairs so that the resulting part is sorted - we compare the elements of one part with the elements of another, respectively, and write them in the necessary order into the resultant one . Then we merge the obtained parts again in pairs, etc., until we have one part left, which will be the sorted array.

The text is difficult to understand, so I recommend to see the graphic demonstration (there is a gif on the same Wikipedia). When you understand the idea, you can already delve into the implementation.

About inversions

When we merge both parts, as I said, we compare the elements of one (first, left) part with the elements of the other (right, second) part, respectively. And if the element of the left side is greater than the element of the right side, respectively, then this is the inverse.
And also all the remaining elements of the left side will also be more, because left and right side sorted. Therefore, the number of inversions must be increased by the number of remaining elements + 1 (current element).

UPD:

Here is an example.

Indexation comes from 0. I did not describe that we add elements to the resulting part, I think this is understandable. Described only those parts in which there is an inversion. Errors are possible, because quickly did. Yes, and I had to fit the elements so compressed that the picture was fully displayed on the hashcode.

alt text

  • Can you give an example of the function? - qwesc
 public static int[] Merge_Sort(int[] arr, ref int counter) { if (arr.Length == 1) return arr; int mid_point = arr.Length / 2; int[] a; Merge(Merge_Sort(arr.Take(mid_point).ToArray(), ref counter), Merge_Sort(arr.Skip(mid_point).ToArray(), ref counter), out a, ref counter); return a; } public static void Merge(int[] mass1, int[] mass2, out int[] merged, ref int counter) { int a = 0, b = 0; merged = new int[mass1.Length + mass2.Length]; for (int i = 0; i < mass1.Length + mass2.Length; i++) { if (b < mass2.Length && a < mass1.Length) if (mass1[a] > mass2[b]) { merged[i] = mass2[b++]; counter = counter + (mass1.Length - a); } else //if int go for { merged[i] = mass1[a++]; } else if (b < mass2.Length) { merged[i] = mass2[b++]; } else { merged[i] = mass1[a++]; } } }
  • Please try to write more detailed answers. I am sure the author of the question would be grateful for your expert commentary on the code above. - Nicolas Chabanovsky ♦
  • Actually this is not the answer to the question posed ... It is a merge sort and not a search for the number of inversions. - pavel