Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Counting Inversions using Merge Sort More...
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
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 () |
Program Body contains all main funtionality. | |
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]
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].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.
arr | - array, data member of std::vector<int>, input for counting inversions |
array_size | - number of elementa in the array |
int main | ( | void | ) |
Program Body contains all main funtionality.
Main function
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.
arr | input array, data-menber of vector |
temp | stores the resultant merged array |
left | lower bound of arr[] and left-sub-array |
mid | midpoint, upper bound of left sub-array, (mid+1) gives the lower bound of right-sub-array |
right | upper bound of arr[] and right-sub-array |
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.
arr | - array to be sorted |
temp | - merged resultant array |
left | - lower bound of array |
right | - upper bound of array |
void sorting::inversion::show | ( | T * | arr, |
const uint32_t | array_size ) |
|
static |
Test implementations.