fork download
copy 
  1. // C++ program to Count 
  2. // Inversions in an array 
  3. // using Merge Sort 
  4. #include <bits/stdc++.h> 
  5. using namespace std; 
  6.  
  7. int _mergeSort(int arr[], int temp[], int left, int right); 
  8. int merge(int arr[], int temp[], int left, int mid, int right); 
  9.  
  10. /* This function sorts the input array and returns the 
  11. number of inversions in the array */
  12. int mergeSort(int arr[], int array_size) 
  13. { 
  14. 	int temp[array_size]; 
  15. 	return _mergeSort(arr, temp, 0, array_size - 1); 
  16. } 
  17.  
  18. /* An auxiliary recursive function that sorts the input array and 
  19. returns the number of inversions in the array. */
  20. int _mergeSort(int arr[], int temp[], int left, int right) 
  21. { 
  22. 	int mid, inv_count = 0; 
  23. 	if (right > left) { 
  24. 		/* Divide the array into two parts and 
  25. 		call _mergeSortAndCountInv() 
  26. 		for each of the parts */
  27. 		mid = (right + left) / 2; 
  28.  
  29. 		/* Inversion count will be sum of 
  30. 		inversions in left-part, right-part 
  31. 		and number of inversions in merging */
  32. 		inv_count += _mergeSort(arr, temp, left, mid); 
  33. 		inv_count += _mergeSort(arr, temp, mid + 1, right); 
  34.  
  35. 		/*Merge the two parts*/
  36. 		inv_count += merge(arr, temp, left, mid + 1, right); 
  37. 	} 
  38. 	return inv_count; 
  39. } 
  40.  
  41. /* This funt merges two sorted arrays 
  42. and returns inversion count in the arrays.*/
  43. int merge(int arr[], int temp[], int left, 
  44. 		int mid, int right) 
  45. { 
  46. 	int i, j, k; 
  47. 	int inv_count = 0; 
  48.  
  49. 	i = left; /* i is index for left subarray*/
  50. 	j = mid; /* j is index for right subarray*/
  51. 	k = left; /* k is index for resultant merged subarray*/
  52. 	while ((i <= mid - 1) && (j <= right)) { 
  53. 		if (arr[i] <= arr[j]) { 
  54. 			temp[k++] = arr[i++]; 
  55. 		} 
  56. 		else { 
  57. 			temp[k++] = arr[j++]; 
  58.  
  59. 			/* this is tricky -- see above 
  60. 			explanation/diagram for merge()*/
  61. 			inv_count = inv_count + (mid - i); 
  62. 		} 
  63. 	} 
  64.  
  65. 	/* Copy the remaining elements of left subarray 
  66. (if there are any) to temp*/
  67. 	while (i <= mid - 1) 
  68. 		temp[k++] = arr[i++]; 
  69.  
  70. 	/* Copy the remaining elements of right subarray 
  71. (if there are any) to temp*/
  72. 	while (j <= right) 
  73. 		temp[k++] = arr[j++]; 
  74.  
  75. 	/*Copy back the merged elements to original array*/
  76. 	for (i = left; i <= right; i++) 
  77. 		arr[i] = temp[i]; 
  78.  
  79. 	return inv_count; 
  80. } 
  81.  
  82. // Driver code 
  83. int main() 
  84. { 
  85. 	int arr[] = { 1, 20, 6, 4, 5 }; 
  86. 	int n = sizeof(arr) / sizeof(arr[0]); 
  87. 	int ans = mergeSort(arr, n); 
  88. 	cout << " Number of inversions are " << ans; 
  89. 	return 0; 
  90. } 
  91.  
  92. // This is code is contributed by rathbhupendra 
  93.  
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
1
5
2 4 1 3 5
stdout
copy 
 Number of inversions are 5
https://ideone.com/96wctY
language:
C++ (gcc 8.3)
created:
4 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!