countInversions

Function

template <typename RandomAccessIterator>

int countInversions (RandomAccessIterator first, RandomAccessIterator last);

Count the number of inversions in the range. The items in the range will not be changed.

Parameters

first, last

Random access iterators to the initial and final positions of the sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Return value

Number of inversions in the range.

Example

#include <iostream>
#include "HKUAL_order.h"

using namespace std;
using namespace HKUAL;
int main(){
    int mylist[] ={1, 3, 5, 4, 2, 0};
    cout << "Number of inversions = " << countInversions(mylist, mylist + 6) << endl;
    return 0;
}

Output

Time Complexity

, n is the number of items in the range.