Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
count_inversions.cpp File Reference

Counting Inversions using Merge Sort More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
Include dependency graph for count_inversions.cpp:

Namespaces

namespace  sorting
 for working with vectors
 
namespace  inversion
 Functions for counting inversions using Merge Sort algorithm.
 

Functions

template<typename T >
uint32_t sorting::inversion::merge (T *arr, T *temp, uint32_t left, uint32_t mid, uint32_t right)
 Function to merge two sub-arrays.
 
template<typename T >
uint32_t sorting::inversion::mergeSort (T *arr, T *temp, uint32_t left, uint32_t right)
 Implement merge Sort and count inverions while merging.
 
template<class T >
uint32_t sorting::inversion::countInversion (T *arr, const uint32_t size)
 Function countInversion() returns the number of inversion present in the input array. Inversions are an estimate of how close or far off the array is to being sorted.
 
template<typename T >
void sorting::inversion::show (T *arr, const uint32_t array_size)
 UTILITY function to print array.
 
static void test ()
 Test implementations.
 
int main ()
 Main function.
 

Detailed Description

Counting Inversions using Merge Sort

Program to count the number of inversions in an array using merge-sort.

The count of inversions help to determine how close the array is to be sorted in ASCENDING order.

two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Time Complexity --> O(n.log n)

Space Complexity --> O(n) ; additional array temp[1..n]

Algorithm

  1. The idea is similar to merge sort, divide the array into two equal or almost equal halves in each step until the base case is reached.
  2. Create a function merge that counts the number of inversions when two halves of the array are merged, create two indices i and j, i is the index for first half and j is an index of the second half. if a[i] is greater than a[j], then there are (mid – i) inversions, Because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
  3. Create a recursive function to divide the array into halves and find the answer by summing the number of inversions is the first half, number of inversion in the second half and the number of inversions by merging the two.
  4. The base case of recursion is when there is only one element in the given half.
  5. Print the answer
Author
Rakshit Raj

Function Documentation

◆ countInversion()

template<class T >
uint32_t sorting::inversion::countInversion ( T * arr,
const uint32_t size )

Function countInversion() returns the number of inversion present in the input array. Inversions are an estimate of how close or far off the array is to being sorted.

Number of inversions in a sorted array is 0. Number of inversion in an array[1...n] sorted in non-ascending order is n(n-1)/2, since each pair of elements contitute an inversion.

Parameters
arr- array, data member of std::vector<int>, input for counting inversions
array_size- number of elementa in the array
Returns
number of inversions in input array, sorts the array
164 {
165 std::vector<T> temp;
166 temp.reserve(size);
167 temp.assign(size, 0);
168 return mergeSort(arr, temp.data(), 0, size - 1);
169}
T assign(T... args)
T data(T... args)
void mergeSort(int *arr, int l, int r)
Definition merge_sort.cpp:71
T reserve(T... args)
Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns
0 on exit
271 {
272 test(); // Run test implementations
273 // body(); // test your own array
274 return 0;
275}
static void test()
Test implementations.
Definition count_inversions.cpp:194
Here is the call graph for this function:

◆ merge()

template<typename T >
uint32_t sorting::inversion::merge ( T * arr,
T * temp,
uint32_t left,
uint32_t mid,
uint32_t right )

Function to merge two sub-arrays.

merge() function is called from mergeSort() to merge the array after it split for sorting by the mergeSort() funtion.

In this case the merge fuction will also count and return inversions detected when merging the sub arrays.

Parameters
arrinput array, data-menber of vector
tempstores the resultant merged array
leftlower bound of arr[] and left-sub-array
midmidpoint, upper bound of left sub-array, (mid+1) gives the lower bound of right-sub-array
rightupper bound of arr[] and right-sub-array
Returns
number of inversions found in merge step
85 {
86 uint32_t i = left; /* i --> index of left sub-array */
87 uint32_t j = mid + 1; /* j --> index for right sub-array */
88 uint32_t k = left; /* k --> index for resultant array temp */
89 uint32_t inv_count = 0; // inversion count
90
91 while ((i <= mid) && (j <= right)) {
92 if (arr[i] <= arr[j]) {
93 temp[k++] = arr[i++];
94 } else {
95 temp[k++] = arr[j++];
96 inv_count +=
97 (mid - i +
98 1); // tricky; may vary depending on selection of sub-array
99 }
100 }
101 // Add remaining elements from the larger subarray to the end of temp
102 while (i <= mid) {
103 temp[k++] = arr[i++];
104 }
105 while (j <= right) {
106 temp[k++] = arr[j++];
107 }
108 // Copy temp[] to arr[]
109 for (k = left; k <= right; k++) {
110 arr[k] = temp[k];
111 }
112 return inv_count;
113}
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
T right(T... args)

◆ mergeSort()

template<typename T >
uint32_t sorting::inversion::mergeSort ( T * arr,
T * temp,
uint32_t left,
uint32_t right )

Implement merge Sort and count inverions while merging.

The mergeSort() function implements Merge Sort, a Divide and conquer algorithm, it divides the input array into two halves and calls itself for each sub-array and then calls the merge() function to merge the two halves.

Parameters
arr- array to be sorted
temp- merged resultant array
left- lower bound of array
right- upper bound of array
Returns
number of inversions in array
132 {
133 uint32_t mid = 0, inv_count = 0;
134 if (right > left) {
135 // midpoint to split the array
136 mid = (right + left) / 2;
137 // Add inversions in left and right sub-arrays
138 inv_count += mergeSort(arr, temp, left, mid); // left sub-array
139 inv_count += mergeSort(arr, temp, mid + 1, right);
140
141 // inversions in the merge step
142 inv_count += merge(arr, temp, left, mid, right);
143 }
144 return inv_count;
145}
void merge(int *arr, int l, int m, int r)
Definition merge_sort.cpp:33
Here is the call graph for this function:

◆ show()

template<typename T >
void sorting::inversion::show ( T * arr,
const uint32_t array_size )

UTILITY function to print array.

Parameters
arr[]array to print
array_sizesize of input array arr[]
Returns
void
179 {
180 std::cout << "Printing array: \n";
181 for (uint32_t i = 0; i < array_size; i++) {
182 std::cout << " " << arr[i];
183 }
184 std::cout << "\n";
185}

◆ test()

static void test ( )
static

Test implementations.

Returns
void
194 {
195 // Test 1
196 std::vector<uint64_t> arr1 = {
197 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84,
198 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67,
199 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50,
200 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33,
201 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
202 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
203 uint32_t size1 = arr1.size();
204 uint32_t inv_count1 = 4950;
205 uint32_t result1 = sorting::inversion::countInversion(arr1.data(), size1);
206 assert(inv_count1 == result1);
207 // Test 2
208 std::vector<int> arr2 = {22, 66, 75, 23, 11, 87, 2, 44, 98, 43};
209 uint32_t size2 = arr2.size();
210 uint32_t inv_count2 = 20;
211 uint32_t result2 = sorting::inversion::countInversion(arr2.data(), size2);
212 assert(inv_count2 == result2);
213 // Test 3
214 std::vector<double> arr3 = {33.1, 45.2, 65.4, 76.5, 1.0,
215 2.9, 5.4, 7.7, 88.9, 12.4};
216 uint32_t size3 = arr3.size();
217 uint32_t inv_count3 = 21;
218 uint32_t result3 = sorting::inversion::countInversion(arr3.data(), size3);
219 assert(inv_count3 == result3);
220 // Test 4
221 std::vector<char> arr4 = {'a', 'b', 'c', 'd', 'e'};
222 uint32_t size4 = arr4.size();
223 uint32_t inv_count4 = 0;
224 uint32_t result4 = sorting::inversion::countInversion(arr4.data(), size4);
225 assert(inv_count4 == result4);
226}
uint32_t countInversion(T *arr, const uint32_t size)
Function countInversion() returns the number of inversion present in the input array....
Definition count_inversions.cpp:164
T size(T... args)
Here is the call graph for this function: